[알고리즘] DFS와 BFS

DFS와 BFS에 대한 감이 잡히지 않아 문제를 반복 풀이하는 중이다.

개념과 용도는 어느정도 습득했고, 백준의 미로 탐색 문제 풀이 삽질 과정을 적어보고자 한다.

우선 DFS로 문제 풀이를 시작했다.

그러나 '최소 거리' 조건을 만족시키기 위해
현재의 거리와 이전 계산된 거리를 비교하는 추가적인 조건이 필요했고, 도착점에 도달 불가능할 때 돌아갈 루트를 저장할 공간이 필요했다. 결국 DFS로 완벽한 코드를 작성하지 못했고 BFS로 코드를 작성하기 시작했다.

코드는 아래와 같다.

from collections import deque

graph = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
for i 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 ny < 0 or nx >= n or ny >= m:
                continue
            elif graph[nx][ny] == 0:
                continue
            elif graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
                
bfs(0, 0)
print(graph[n - 1][m - 1])

구현을 마무리한 후 다시 생각해보니 당연하게도 BFS를 채택했어야 했다.

BFS는 너비 우선 탐색 방법으로, 현재 노드와의 가까운 거리 노드가 우선이 된다.
이러한 특징을 통해 추가적인 조건 없이도 최소 조건을 만족시킬 수 있었다.