[이것이 코딩테스트다] BFS 문제풀이 - 미로 탈출

문제 설명

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

 

 

코드

from collections import deque

# n, m 입력받기
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 = deque()
    queue.append((x,y))
    
    # queue가 빌 때까지 반복
    while queue:
    	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:
            	graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    # 가장 오른쪽 아래의 최단 거리 변환
	return graph[n-1][m-1]
 # (0,0) 시작 위치 / (n, m) 마지막 위치
 print(bfs(0,0))

 

문제를 푼 후 생각 정리

○ 한 위치에서 다른 위치까지의 거리를 구하는 문제를 보고 그래프 탐색 문제임을 파악했습니다.

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하는 알고리즘이므로 BFS를 사용하였습니다.

 

○ 시작위치 (0, 0)부터 시작하여 상하좌우 4방향을 확인합니다. 첫 번째로 이동할 수 없는 부분은 무시하기 위해서 if문을 통해 지나가게 짰습니다. (graph[a][b]가 0인 경우 또는 (0<=a<n and 0<=b<m) 범위를 벗어나는 경우를 무시합니다.)

 

○ graph[nx][ny]가 1인 경우 이동할 수 있는 칸이므로 이동을 한 뒤 +1을 하여 움직이는 칸의 개수를 카운트합니다.

(저는 칸을 움직이면서 +1씩 하는 것은 이해가 됐지만, 연산 이후에 지나간 곳을 다시 지나가는 경우는 어떻게 되는지 헷갈렸습니다. 

-> bfs 알고리즘은 시작 노드에서 가까운 노드를 하나씩 탐색하기에, 위 문제에서 이동한 칸은 +1 연산되어 더 이상 1의 값이 아니기에 무시가 되므로 문제가 되지 않습니다. 이 알고리즘을 통해 같은 곳을 반복해서 지나지 않으므로 최소 칸의 개수를 구할 수 있다는 것을 이해했습니다. )