문제
N×M크기의 배열로 표현되는 미로가 있다.
| 1 | 0 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력 1
1
2
3
4
5
4 6
101111
101010
101011
111011
예제 출력 1
1
15
예제 입력 2
1
2
3
4
5
4 6
110110
110110
111111
111101
예제 출력 2
1
9
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from collections import deque
def bfs(x, y):
# queue 생성
queue = deque()
# 큐에 첫 시작 지점 넣기
queue.append((x, y))
while queue: # 큐가 비어있지 않다면
x, y = queue.popleft() # 큐에서 pop
for i in range(4): # 상 하 좌 우, 이동할 수 있는 지점 체크
nx = x + dx[i]
ny = y + dy[i]
# 범위 밖으로 나간다면 무시
if nx < 0 or ny < 0 or nx > N-1 or ny > M-1:
continue
# 벽이라면 무시
if graph[nx][ny] == 0:
continue
# 이동할 수 있고, 처음 방문한다면
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1 # 다음 위치 = 그래프 전 위치 +1
queue.append((nx, ny)) # 큐에 다음 위치 삽입
# 마지막 그래프 좌표의 값 == 이동횟수 출력
return graph[N-1][M-1]
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]
print(bfs(0, 0))
정리
미로탐색 문제는 BFS(너비 우선 탐색)을 사용하여 푸는 문제였다. 우선 BFS는 기본적으로 큐를 사용하여 푸는데, 파이썬 리스트로 구현하는 것 보다 collections의 deque (덱) 을 사용해서 풀면 시간복잡도 측면에서 낫다고 한다. 큐를 구현해서 첫 지점을 큐에 넣는 것으로 시작해서 상, 하, 좌, 우, 위치를 살펴보며 1. 그래프 범위 밖인지, 2. 벽인지 두 가지 조건으로 예외 처리를 해준다. 한 칸 이동할 때마다 해당 좌표의 값을 1에서 이전 값 만큼 더해서 얼마나 이동한지 표시해주는 방법이 중요하다. 마지막으로 탈출구의 좌표값에 들어있는 이동한 거리를 출력해준다.
어려웠던 점
만약
1 1 1
0 1 0
0 1 1
같은 그래프라면, (0,2)로, 길이없는 곳으로 잘못 이동했을 경우에는 어떻게 처리되는지 헷갈렸다. 하지만 방문할 때마다 이동 거리를 더해주기 때문에 재방문은 하지 않고 상하좌우가 뚫려있는 곳으로 이동할 수 있었다.
