Iridescent Seraphim

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

문제 풀이)

이거는 BFS 방식으로 풀 수 있다. 왜냐하면, 문제에서도 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라고 했고, 출력 조건도 첫째 줄에 최소 이동칸의 개수를 출력한다고 했기 때문이다.
DFS는 일단 끝까지 진행해서 어디가 가능한 지를 보기 때문에 여러 번 왔다 갔다 할 수 있다. 그렇기에 최단거리가 보장이 안되는 반면, BFS는 가까운 곳부터 퍼져나가는 방식을 사용해서 효율적으로 움직이기 때문에 최단거리를 보장한다.
BFS (Breadth-First Search)란 너비 우선 탐색으로 그래프나 맵에서 한 지점에서 시작해 인접한 칸을 먼저 전부 탐색한 뒤, 그 다음 거리의 칸을 탐색하는 방식이다. 마치 돌을 물에 던졌을 때 물결이 동심원처럼 퍼져나가는 것과 같다.
DFS와 달리 가까운 곳부터 순서대로 탐색하기 때문에 최단 거리를 보장한다는 특징이 있다. 이 때문에 “최소 몇 칸을 이동해야 하는가” 와 같은 최단 경로 문제에 적합하다. 큐(Queue) 자료구조를 사용하며, 먼저 넣은 칸을 먼저 꺼내는 방식으로 동작한다.
이 문제에서는 BFS를 이용해 시작점 (0, 0) 에서 출발해 상하좌우로 퍼져나가며 도착점 (N-1, M-1) 까지의 최단 거리를 구한다. 이동할 때마다 해당 칸의 값을 이전 칸의 값 + 1로 갱신해 거리를 기록하며, 도착점에 도달했을 때의 값이 곧 최소 이동 칸의 개수가 된다.

이전 문제들과 마찬가지로 맵의 크기를 N과 M으로 입력받고(N × M), 맵 정보는 graph 변수에 저장한다. 공백 없이 붙어서 입력되므로 DFS와 마찬가지로 split() 없이 한 글자씩 받는다.

앞에서 배운대로 queue 를 사용해 시작점 (0, 0) 을 먼저 넣고 탐색을 시작한다. 큐에서 꺼낸 칸의 상하좌우를 확인하면서, 범위를 벗어나거나 괴물(0)이 있는 칸은 스킵한다. 처음 방문하는 칸(1)이라면 이전 칸의 값에 +1 을 더해 거리를 기록하고 큐에 넣는다. 이 과정을 반복하다 보면 도착점 (N-1, M-1) 에 최단거리가 기록되고, 그 값을 반환하면 끝이다.

from collections import deque
N, M = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
graph = []
for _ in range(N):
    graph.append(list(map(int, input())))
# 시작점을 매개변수로 받아서 나중에 바꿀 수 있게 함
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 nx >= N or ny < 0 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] # 최단 거리 반환
print(bfs(0, 0))

BFS는 DFS에 비해 확실히 어려웠다. 상하좌우 문제나 맵 문제는 이제 익숙해졌지만, BFS 특유의 큐 방식이나 graph[nx][ny] = graph[x][y] + 1 로 거리를 기록하는 방식은 직접 한 칸씩 따라가보기 전까지는 이해가 안 됐다. 물론 여러 번 비슷한 문제를 풀다 보면 감이 잡히겠지만, 지금 당장은 아직 내 것으로 완전히 만들지 못한 느낌이다.

입력 예시를 준 대로 입력해보면 아래처럼 결과가 나온다.

답안 예시 코드와 거의 동일하게 나왔다. AI의 도움을 받긴 했지만, 각 단계를 이해하면서 풀었기 때문에 의미 있는 풀이였다고 생각한다.
그도 그럴 것이 애초에 BFS 순서를 이해하는 것도 두 번 봐야 이해가 갔다면… 뭐 말 다한 정도지 않을까..ㅠㅠ
직관적인 DFS에 비해 BFS는 순서가 살짝 헷갈리긴 했지만 그래도 노드 움직이는 순서는 이해했는데, 막상 문제를 풀려고 하니 알듯 말듯해서 ai 도움을 좀 많이 받았다…

BFS 문제에서 솔직히 처음에 뭘 모르는지도 몰랐다. DFS는 상하좌우를 직접 dfs(x-1, y), dfs(x+1, y) 이렇게 써줬는데, BFS에서는 왜 for i in range(4) 로 묶는지부터 이해가 안 됐다. 알고 보니 결과는 똑같고 그냥 for문으로 줄인 것뿐이었는데, 그걸 모르니까 코드 자체가 낯설게 느껴졌던 것 같다.

그리고 queue.append((x, y)) 가 왜 시작점이 되는지도 헷갈렸다. 책에서는 visited[start] = True 로 방문처리를 따로 했는데, 여기서는 그런 게 없으니까 어디서 시작하는 건지 감이 안 왔다. 알고 보니 bfs(0, 0) 으로 호출할 때 x=0, y=0 이 함수로 들어가고, 그게 큐에 들어가는 거였다. 당연한 건데 당연하게 안 느껴졌다.

제일 오래 걸린 건 역시 graph[nx][ny] = graph[x][y] + 1 이 왜 최단거리가 되는지였다. DFS에서는 result += 1 로 덩어리 개수를 셌는데, 여기서는 왜 그래프 값 자체를 바꾸는지 전혀 이해가 안 됐다. 설명을 들어도 모르겠어서 결국 (0,0) 에서 (4,5) 까지 한 칸씩 직접 따라가봤다.

시작점 (0,0) = 1 에서 출발해서 아래 (1,0) 으로 이동하면 1+1=2, 거기서 오른쪽 (1,1) 으로 가면 2+1=3… 이렇게 한 칸씩 따라가다 보니까 도착점 (4,5) 에 10 이 기록되는 과정이 눈에 보였다. 중간에 숫자가 겹치는 칸도 있었는데, 그건 시작점에서 같은 거리만큼 떨어진 칸들이라 겹쳐도 상관없다는 것도 그때 이해했다.

BFS는 가까운 곳부터 퍼져나가기 때문에 도착점에 처음 닿는 순간이 최단거리임이 보장된다. 그래서 4, 5번째 줄 왼쪽 칸들은 굳이 탐색할 필요가 없고, return graph[N-1][M-1] 한 줄로 끝낼 수 있는 거였다. 직접 따라가보기 전까지는 진짜 하나도 몰랐는데, 한 칸씩 보고 나니까 그제서야 이해가 됐다.