[이취코테] 미로 탈출

https://www.youtube.com/watch?v=7C9RgOcvkvo 

이 문제의 해설 영상이다.

문제

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

 

입력 조건:

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

 

출력 조건: 첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

정답 코드

from collections import deque
n, m = map(int, input().split())
graph = [list(map(int, input())) for i in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def bfs(x, y):
    queue = deque()
    queue.append((x,y))
    
    while queue:
        x, y = queue.popleft()
        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] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
        
    return graph[n-1][m-1]

print(bfs(0,0))

이 문제는 시작 지점에서 가까운 노드부터 차례로 탐색하면 되기 때문에 BFS 알고리즘으로 풀 수 있겠다고 생각하였다. 하지만 BFS를 처음 활용해보는 문제라 끝까지 풀지 못하였다. 

 

이 문제도 역시 탐색 문제이므로 방향벡터를 이용해서 노드를 이동하는 방법이 기본이 되었다. 

책에 있는 솔루션에서는 노드를 옮겨 갈 때마다 그 노드까지 걸린 최단 거리로 그 노드의 숫자를 바꿔주는 방식을 사용하였다. 이렇게 하면 따로 visited 처리를 안해줘도 되고 cnt 변수를 따로 안두어도 되는 것이 특징인것 같다. 

 

배울 점

최단경로 문제를 많이 풀어보며 bfs 알고리즘에 익숙해질 수 있도록 해야겠다.

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)