백준 2206번 벽 부수고 이동하기

최단경로니까 bfs를 쓰긴해야하는데 dp를 곁들인 bfs를 써야한다.

 

from collections import deque
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
in_board=[]
graph=[[] for _ in range(n)]
for i in range(n):
    in_board.append(sys.stdin.readline().rstrip())
for i in range(n):
    for j in in_board[i]:
        graph[i].append(ord(j)-ord('0'))

v=[[[-1]*2 for _ in range(m)]for _ in range(n)]
q=deque()
q.append([0,0])
v[0][0][0]=1
v[0][0][1]=1
dr=[-1,0,1,0]
dc=[0,1,0,-1]
while q:
    cur_row,cur_col=q.popleft()
    for i in range(4):
        row=cur_row+dr[i]
        col=cur_col+dc[i]
        if row>=n or row<0 or col>=m or col<0:
            continue

        if v[cur_row][cur_col][0]==-1:
            if graph[row][col]==1:
                continue
            if v[row][col][1]==-1 or v[row][col][1]>v[cur_row][cur_col][1]+1:
                v[row][col][1]=v[cur_row][cur_col][1]+1
                q.append([row,col])
            continue
        
        if graph[row][col]==1:
            if v[row][col][1]==-1 or v[row][col][1]>v[cur_row][cur_col][0]+1:
                v[row][col][1]=v[cur_row][cur_col][0]+1
                q.append([row,col])
        else:
            if v[row][col][0]==-1 or v[row][col][0]>v[cur_row][cur_col][0]+1:
                v[row][col][0]=v[cur_row][cur_col][0]+1
                q.append([row,col])

print(max(v[n-1][m-1][0],v[n-1][m-1][1]))

신경쓸게 너무 많아서 if로 떡칠됐다

또 시작정점을 1로 세야한다.

아...

 

최단경로이기때문에 마지막에 min을 써야한다

 

from collections import deque
import sys

n,m=map(int,sys.stdin.readline().rstrip().split())
in_board=[]
for i in range(n):
    in_board.append(sys.stdin.readline().rstrip())

v=[[[-1]*2 for _ in range(m)]for _ in range(n)]
q=deque()
q.append([0,0])
v[0][0][0]=1
v[0][0][1]=1
dr=[-1,0,1,0]
dc=[0,1,0,-1]
while q:
    cur_row,cur_col=q.popleft()
    for i in range(4):
        row=cur_row+dr[i]
        col=cur_col+dc[i]
        if row>=n or row<0 or col>=m or col<0:
            continue

        if v[cur_row][cur_col][0]==-1:
            if in_board[row][col]=='1':
                continue
            if v[row][col][1]==-1 or v[row][col][1]>v[cur_row][cur_col][1]+1:
                v[row][col][1]=v[cur_row][cur_col][1]+1
                q.append([row,col])
            continue
        
        if in_board[row][col]=='1':
            if v[row][col][1]==-1 or v[row][col][1]>v[cur_row][cur_col][0]+1:
                v[row][col][1]=v[cur_row][cur_col][0]+1
                q.append([row,col])
        else:
            if v[row][col][0]==-1 or v[row][col][0]>v[cur_row][cur_col][0]+1:
                v[row][col][0]=v[cur_row][cur_col][0]+1
                q.append([row,col])

if min(v[n-1][m-1][0],v[n-1][m-1][1])==-1:
    print(max(v[n-1][m-1][0],v[n-1][m-1][1]))
else:
    print(min(v[n-1][m-1][0],v[n-1][m-1][1]))

단순하게 생각해서 이렇게 고치면 되지않을까(속도향상을 위해서 숫자로 변환하는 과정도 뺐다)

캬

(14시간 전인 이유는 처음낼때 새벽4시라서 자고 일어나서 알바하고 돌아와서 수정한거라서 그럼)

물론 내 코드보다 훨씬 깔끔한 코드가 q에 애초에 이전상태의 값을 넣어놓고 오는게 훨씬 간단하다.