BOj 2178. 미로찾기 (BFS)

현재 시점을 큐에 넣고 그 다음 좌표값으로 동서남북으로 움직이며 계속 탐색하는 방법으로 접근

다음 좌표의 값이 0이면 패스, 1이면 이전 값에 누적시키며 기록하여 최종 기록 나올 때까지 탐색하게 된다.

 

from collections import deque
#bfs 문제

n, m = map(int, input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int,input())))

#상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]




def bfs(x, y):
    #queue 선언
    queue = deque()
    queue.append((x, y))

    #큐가 빌 때까지
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0  or nx >= n or ny<0 or ny >= m:
                continue
            
            #해당 미로가 0인경우 무시
            if graph[nx][ny] == 0:
                continue
            
            if graph[nx][ny] == 1:
                #현재 좌표에 이전 값에 1 더한걸로 기록
                graph[nx][ny] = graph[x][y] + 1
                
                #다음 좌표로 넘기기 위해 큐에 넣기
                queue.append((nx,ny))
    
    
    return graph[n-1][m-1]

print(bfs(0,0))