[백준 알고리즘: python 3] #2178 - 미로탐색(BFS 스터디)

https://www.acmicpc.net/problem/2178

 

2178번 문제는 알고리즘 스터디에서 BFS 주제로 잡은 문제입니다. 기본적인 BFS 문제인 것으로 생각이 될 정도의 난이도인 것 같고 연습하기에 좋은 것 같습니다.

 

Breadth First Search(너비 우선 탐색)의 줄임말인 BFS는 깊이 우선 탐색인 DFS 와 함께 소개가 되고는 합니다. 노드를 전부 탐색한다는 점에서 비슷하지만 탐색하는 방식의 차이 때문에 각각의 방법으로 풀 수 있는 문제가 구분되기도 하기 때문인데요, 미로에서 시작 지점부터 도착 지점까지 최소거리를 구하는 이번 문제가 대표적인 BFS 문제로 여겨지는 것 같습니다.

 

BFS는 DFS와는 달리 재귀적인 함수의 형태를 가지지 않는 점과, Queue 자료 구조를 사용한다는 점이 다릅니다. 따라서, 복잡도가 높지 않은 편이고 Queue에 대한 지식이 있다면 구현하기도 그렇게 어렵지는 않습니다. 다만, 이 둘은 같은 알고리즘은 아니고 탐색의 방식이 다르기 때문에 목적에 따라 구분되어야 한다는 점을 유의해야 합니다. 그래프의 경로에 대한 정보가 문제 풀이의 핵심이라면 DFS를, 그래프 전체적인 정보의 문제라면 BFS를 떠올리게 되는 것 같아요. BFS의 그림을 통한 자세한 설명은 이 블로그에 잘 정리되어 있습니다. 참고하시길 바랍니다.

 

Hint!

저로서는 이번 문제를 BFS의 개념을 그대로 구현한다고 풀 수는 없었습니다. 미로의 도착 최단 거리를 구하기 위해서는 BFS로 탐색의 범위를 늘려가면서 도착지점이 탐색되는 순간의 Depth를 찾는 것이 이 문제의 관건이기 때문입니다. 이 Depth는 BFS를 실행할 때 시작 지점으로부터 간선을 몇 개를 지나쳤는가로 계산이 될 수 있습니다.

 

위의 블로그를 참고해서 공부를 해봤을 때는, 깊이와 상관없이 탐색을 하는 것이기 때문에 Queue에 있는 노드들을 하나씩 순회합니다. 이 경우에는 현재 몇 번째 Depth로 진행 중인지 알 수가 없어요. 그래서 저는 Queue에 있는 노드를 하나씩 가져오면서 그때그때 인접한 노드를 Queue에 추가하는 것이 아니라, Depth마다 Queue의 노드를 모두 순회할 때까지 인접한 노드를 추가하지 않고 따로 모아뒀다가 다음 Depth의 Queue로 업데이트 한 뒤에 다시 순회를 하는 방식을 택했습니다. 이러면 현재 순회중인 Queue가 몇 번째 Depth의 것인지 확인할 수 있고 Queue에서 만약 도착 지점의 노드가 확인되었다면 그 때의 Depth가 답이 된다고 할 수 있습니다.

 

아래의 코드의 주석 처리된 print 함수를 풀고 실행해 보시면 각 Depth마다 어떤 노드들이 그 Depth에 속하는지 순차적으로 확인해보실 수 있습니다. 참고해주세요! 아래의 코드로 성공했습니다. 어렵지 않으니 천천히 살펴봐주세요!

 

import sys

def bfs(maze, N, M):
    depth = 0
    queue = [(0, 0)]
    visited = [[False for _ in range(M)] for _ in range(N)]
    visited[0][0] = True

    while queue:
        # 다음 Depth의 Queue를 위한 임시 리스트
        next_queue = []
        depth += 1
        # print("depth", depth, ":", queue)
        if (N-1, M-1) in queue: break
        for x, y in queue:
            if x == N-1 and y == M-1: break
            visited[x][y] = True
            adjacents = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
            for ax, ay in adjacents:
                if 0 <= ax < N and 0 <= ay < M:
                    if maze[ax][ay] and not visited[ax][ay]:
                        visited[ax][ay] = True
                        # 이런식으로 모아둔 뒤에
                        next_queue.append((ax, ay))
        # 다음 Depth의 Queue로 업데이트 합니다.
        queue = next_queue

    return depth

N, M = map(int, sys.stdin.readline().split())

maze = []
for _ in range(N): maze.append(list(map(int, sys.stdin.readline().replace('\n', ''))))
print(bfs(maze, N, M))