[이코테] BFS - 미로 탈출

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

N by M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 괴물이 있어 이를 피해서 탈출해야 한다. 유저의 초기 위치는 (1, 1)이고 미로의 출구는 (N, M) 위치에 존재하며 한 번에 한 칸 씩 이동이 가능하다. 이 때 괴물이 있는 부분은 0, 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 유저가 미로를 탈출하기 위해 움직여야 할 최소 칸의 개수를 구해라. 단, 칸을 셀 때 시작, 마지막 칸도 포함시켜야 한다.

입력조건

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

출력조건

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

사고과정

• 못 풀었다. 아이디어가 전혀 떠오르지 않았다. BFS는 큐를 활용할거야를 생각했지만 아이디어가 떠오르지 않았다.. 그래서 재빨리 풀이를 보았다..
• 풀이를 보았을 때, 해결 아이디어는 "방향 스킬" + "BFS 구현하는 큐" 였다. 우선 괴물이 있는지 없는지 판단하기 위한 것을 그동안 활용한 "방향 스킬"을 활용했다. BFS'만'을 활용할 거라고 제멋대로 생각해서 사고의 폭을 넓히지 못한 듯 하다..
• 큐를 활용하는 코드는 예제와 비슷해서 금방 이해가 된 듯하다. 물론 정답을 보고 나서니깐... 첫 좌표를 큐에 담고 popleft한 다음 이 좌표랑 인접하면서 조건에 맞는 좌표들을 다시 큐에 넣고 그리고 큐에서 또 좌표를 빼내고... 하는 식이었다.
• 풀이의 또 하나의 포인트는 최소 칸의 개수를 구할 때, 갈 수 있는 칸의 값이 모두 1이었다는 점이다. 그래서 칸을 진전할 때마다 1값을 더해서 자동으로 거리를 계산하도록 풀이가 작성되었다(WOW~, 만약 괴물이 1, 갈 수 있는 칸이 0이었다면 이 값들을 서로 change해도 되었을 듯? 응용하면..?) 
• 풀이를 보니 DFS도 그렇고 BFS도 마찬가지로 하나의 함수로 만들어서 구현을 한다.

풀이

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

# Point1) 방향 스킬!
dx = [1, -1, 0, 0]
dy = [0 , 0, 1, -1]

def bfs(x, y):
    # Point2) 데큐 사용!
    queue = deque([(x, y)])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx <= -1 or nx >= n or ny <= -1 or ny >= m:
                continue
            elif graph[nx][ny] == 0:
                continue
            # 해당 노드를 처음 방문한 경우에만 계산해야 하므로 elif 처리해줌(else처리하면 재방문한 노드임에도 거리 계산하게 됨)
            elif graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1  # Point3) 거리계산을 노드에 있는 값으로!
    return graph[n-1][m-1]

print(bfs(0, 0))