BFS의 우선탐색 (appendleft 로 우선탐색후 조건 탐색) - 백준 1261

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 

 

 이 문제는 BFS 문제이긴 하지만 한가지 조건이 있다. 바로 graph에서 1(벽)인 부분을 깨고 진행할 수 있다는 점이다.

 그러므로 visited 배열을 잘 사용해야 하는데 최단거리를 저장하는것이 아닌 1이 만났을때만 count를 올려주는 방법이 좋다.

 또한 graph 내에서 0들만 먼저 탐색할 수 있도록(벽을 최소한 부신다고 했다) appendleft 함수를 사용해서 탐색할수 있는 0은 다 탐색하고 그 다음부터 벽을 부수고 진행할수 있도록 한다.

 

import sys
from collections import deque
M,N=map(int,sys.stdin.readline().split())

graph=[]
for _ in range(N):
    s=sys.stdin.readline().strip()
    s=' '.join(s)
    graph.append(list(map(int,s.split())))

q=deque()
q.append([0,0])
drc=[[1,0],[-1,0],[0,1],[0,-1]]  # 우 좌 남 북
visited=[[-1]*M for _ in range(N)]


visited[0][0]=0


while q:
    row,col=q.popleft()
    
    for dr,dc in drc:
        newr,newc=row+dr,col+dc
        
        if 0<=newr<N and 0<=newc<M:
            if visited[newr][newc]==-1:
                
                if graph[newr][newc]==0:
                    visited[newr][newc]=visited[row][col]
                    q.appendleft([newr,newc])
                    
                else:
                    visited[newr][newc]=visited[row][col]+1
                    q.append([newr,newc])
                

print(visited[N-1][M-1])