[BFS] 미로 탈출

- 문제

주인공은 NxM 크기의 직사각형 형태의 미로에 갇혀 있다. 주인공의 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0 없는 부분은 1로 표시되어 있다. 이 때 주인공이 탈출하기 위해 움직여야하는 최소 칸의 개수를 구하시오. 단 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

- 해설

BSF로 풀 수 있는 문제. BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다. 

그러므로 (1,1) 지점에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다. 

 

from collections import deque

n,m = map(int, input().split())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int,input().split())))

# 이동할 방향 정의, 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))         # 처음 값 큐에 저장

    while queue:
        x,y = queue.popleft()   # 큐에서 빼서 x,y에 저장
        # 현재 위치에서 상하좌우 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx<0 or ny<0 or nx >=n or ny >=m :   # 공간 벗어난 경우 무시
                continue
            if graph[nx][ny]==0:                    # 벽인 경우 무시
                continue
            if graph[nx][ny]==1:                    # 이동할 수 있는 경우 -> 해당 노드에 거리 정보 저장
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))               # 큐에 방문한 위치 저장 
                                                    # -> 이 위치를 다시 위에서 .popleft() 해서 빼서 x,y에 넣고 반복
    return graph[n-1][m-1]

print(bfs(0,0))