[Algo] BFS로 최단거리 구하기 / 백준 2178 - 미로 탐색

모든 점을 다 방문해보아야 하는 DFS와 달리, BFS로 찾은 경로는 도착점이 나오는 즉시 최단거리임을 알 수 있어서 바로 종료할 수 있는 장점이 있다. 따라서 최단거리를 구하는 문제에서는 BFS를 쓰는것이 좋다. 

 

코드를 어떻게 짤까 복잡하게 생각했었는데 bfs()를 콜 하고 제일 먼저 도착점과 같아질 때 끝인것이었다..!

 

백준 2178번을 풀이하면서 작성한 코드는 다음과 같다. 

# 2178번 미로 탐색
# bfs로 탐색해서 제일 먼저 끝점이랑 같아질 때 리턴.
import sys

N, M = map(int, sys.stdin.readline().split())
data = []
for _ in range(N):
    data.append([int(d) for d in str(sys.stdin.readline().rstrip())])
# print(data)
queue = []


def bfs(row, col):
    queue.insert(0, [row, col, 1])
    while queue:
        current = queue.pop()
        newRow = current[0]
        newCol = current[1]
        dist = current[2]

        if newRow == N-1 and newCol == M-1: # 끝점 도달
            break

        # 이웃 찾기
        for a in [-1, 1]:
            if 0 <= (newRow - a) < N:
                if data[newRow - a][newCol] == 1:
                    queue.insert(0, [newRow - a, newCol, dist + 1])
                    data[newRow - a][newCol] = -1 # 큐에 또 들어가는것 방지
        for b in [-1, 1]:
            if 0 <= (newCol - b) < M:
                if data[newRow][newCol - b] == 1:
                    queue.insert(0, [newRow, newCol - b, dist + 1])
                    data[newRow][newCol - b] = -1 # 큐에 또 들어가는것 방지
        data[newRow][newCol] = -1
    print(dist)


bfs(0, 0)

build in Pypy3