문제
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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
문제를 보고 든 생각
이걸 어떻게 해야 되지?
bfs로는 개수 세는 거만 기억이 나는데 dfs로 푸는 문제 아니야?
나의 아이디어
문제를 더 읽고 코드 편집기 위에서 생각을 좀 해보니
해결 방법이 떠올랐다.
bfs로 충분이 해결이 가능하다고 판단이 섰다.
0은 벽이고 1이 있는 곳만 이동할 수 있다.
그리고 문제가 요구하는 사항은 입력값인 n과 m 위치까지 가는 데 걸리는 최소 거리이다.
방법은 아래와 같다.
bfs로 동서남북을 탐색한다.이때, 새롭게 탐색할 좌표의 요소가 0이거나 미로의 크기를 벗어나면 덱에 넣지 않는다.그리고 덱에 들어있는 좌표를 기준으로 다시 동서남북을 탐색한다.
중요한 건 문제의 요구사항인 미로의 종착지까지 가는 데 걸리는 최소 거리이므로새로운 좌표로 이동할 때마다 이전의 좌표까지 온 값에 +1을 더해준다.
코드를 보면 이해가 될 것 같다.
결과
from collections import deque
n, m = map(int, input().split())
maze = []
for _ in range(n):
maze.append(list(map(int, input())))
def mazing(maze, n, m):
q = deque([(0, 0)])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while q:
x, y = q.popleft()
if x == n - 1 and y == m - 1:
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != 0:
if maze[nx][ny] == 1:
maze[nx][ny] = maze[x][y] + 1
q.append((nx, ny))
return maze[n - 1][m - 1]
print(mazing(maze, n, m))
일단 코드의 흐름은 나의 아이디어에서의 설명과 같다.
핵심만 말하려고 한다.
핵심은 여기에 있다고 생각한다.
if maze[nx][ny] == 1:
maze[nx][ny] = maze[x][y] + 1
q.append((nx, ny))우선 위에서 언급했던 것처럼 이전의 좌표값 + 1을 새로운 좌표에 저장한다. 그럼 이것이 거리를 측정하는 행동이 되는 것이다.
그러나 이렇게 적어도 if문을 적지 않는다면 메모리 초과, 무한 반복의 늪에 빠지게 된다.
if문 즉, 새로 탐색한 좌표의 값이 1일 때만 덱에 넣어주는 것으로 설정해주지 않는다면 따로 방문 체크를 하지 않았기 때문에 이전에 탐색했던 좌표로 다시 되돌아갈 가능성이 있다.
그렇게 된다면 bfs가 미로의 중간에서 빠져나오지 못하게 된다.
그래서 방문 측정의 의미로서, 이미 변해버린 값으로는 bfs가 다가가지 않도록 설정해주는 것이 중요하다.
저 조건을 떠올리려고 약 40분은 헤맨 것 같다.
그래도 떠올라서 행복하다.
느낀 점
BFS문제 혹은 DFS문제는 풀었을 때의 희열감이 장난이 아닌 것 같다.
첫인상이 아주 안 좋았던 친구들이라 더 그런 것 같다.