미로탈출 (BFS)
‘BFS를 활용, Python으로 작성’
문제
동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력조건
첫째 줄에 두 정수 N, M(4 <= N, M, <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력조건
첫째 줄에 최소 이동 칸의 개수를 출력.
입력 예시
5 6
101010
111111
000001
111111
111111
출력 예시
10
이런식의 간선 길이가 모두 같을 경우 최단거리 구하는 문제는 BFS를 이용하여 해결할 수 있다. BFS는 가까운 노드부터 방문하여 간선 길이가 같을 경우 최단거리를 구할 수 있기 때문이다. 이동할수록 다음 노드의 값을 증가 시켜서 목적지까지의 최단 거리를 반환하는 방법으로 진행해야 한다. 거리를 갱신하면서 가는게 제일 중요하다!
우선 n, m을 map함수를 이용하여 int로 각각 입력 받고, 이후에 미로의 정보를 입력받아 2차원 그래프로 만든다.
from sys import stdin
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, stdin.readline().rstrip())))
그리고 방문하는 곳의 상하좌우를 탐색하기 위해 상하좌우에 대응하는 x와 y의 증감에 대응하는 dx, dy 리스트를 생성한다.
## 이동할 4가지 방향(상하좌우) 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
그리고 bfs함수에 처음 시작하는 0, 0을 입력해주면 된다.
## bfs 실행
print(bfs(0, 0))
bfs함수에서 deque 라이브러리를 이용하여 큐를 생성한 후, 입력받은 x, y 쌍을 큐에 집어넣는다.
queue = deque()
queue.append((x, y))
큐가 빌때까지 큐에서 뽑아서 뽑은 값을 새로운 x, y인 nx, ny로 초기화 해주고 상하좌우를 확인해야 하므로 4번의 반복을 통해 해당 위치가 갈수 있는 자리인지, 범위를 넘어간 위치인지, 괴물이 있는 갈 수 없는 위치인지 체크를 한다. (0,0)에서 시작하므로 0보다 작은 경우 범위를 벗어나게 된다. 또한 n X m의 그래프이므로 x가 n 이상이거나 y가 m 이상이어도 범위를 벗어난다.이런 경우 무시하고 다음 반복을 진행하기 위해 continue를 이용한다.
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
또한 graph에서 값이 0인 곳도 갈수 없기 때문에 무시하고 다음 반복을 진행한다.
if graph[nx][ny] == 0:
continue
값이 1인 경우는 첫번째 방문한 노드이므로 해당노드의 값을 이전 노드의 값만큼 더해주고 해당 그래프의 좌표를 큐에 넣어준다.
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
이런식으로 계속 큐가 빌때까지 반복하면 그래프의 제일 마지막인 우측 하단에 최단거리가 입력된다. 그래프의 마지막 노드 좌표를 반환하면 해당 그래프의 값이 결국 최단거리가 되는 것이다.
return graph[n - 1][m - 1]
전체 소스 코드
from sys import stdin
from collections import deque
def bfs(x, y):
queue = deque()
queue.append((x, y))
## 큐가 빌 때까지 반복
while queue:
x, y = queue.popleft()
## 현재 위치에서 4가지 방향(상,하,좌,우) 확인
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))
## 가장 우측 하단까지의 거리 반환
return graph[n - 1][m - 1]
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, stdin.readline().rstrip())))
## 이동할 4가지 방향(상하좌우) 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
## bfs 실행
print(bfs(0, 0))
