BFS - 그래프 탐색을 위한 너비 우선 탐색 알고리즘

BFS

 BFS는 Breadth First Search, 너비 우선 탐색이라고도 부르며, 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다고 했는데, BFS는 그 반대다. 그렇다면 BFS는 실제로 어떤 방식으로 구현할 수 있을까? BFS 구현 에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

 

- Part 02 Chapter 05 DFS/BFS 143p

---

알고리즘의 정확한 동작 방식은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복한다.

BFS를 이용하여 탐색하면 그 과정은 다음과 같다. 마찬가지로 인접한 노드가 여러 개 있을 때, 숫자가 작은 노드부터 먼저 큐에 삽입한다고 가정한다. 그다음 큐에 원소가 들어올 때, 위에서 들어오고 아래쪽에서 꺼낸다고 가정하자. 코드로 나타내면 다음과 같다.

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

 

1. 1번 노드부터 시작한다. 1번 노드가 큐에 들어가고 방문처리가 된다. 그리고 반복문(큐의 원소가 존재하는 한)을 실행하고 큐에서 가장 먼저 들어간 원소하나를 추출한다. 해당 노드와 연결된 모든 노드에 대해서 방문하지 않았으면 작은 순서대로 전부 큐에 추가하고 방문하지 않았으면 방문처리가 된다. 현재 1, 2, 3, 8이 방문처리가 되었고 큐에는 2, 3, 8이 존재한다. 출력은 '1 '.
2. 큐에 원소가 추가되었으므로 반복문이 다시 실행된다. 먼저 2번 노드가 빠지고, 연결된 1, 7, 8 중, 방문되지 않은 7이 큐에 추가된다. 현재 큐에는 3, 8, 7이 존재하고 출력은 '1 2 '.
3. 이제 3번 노드가 빠지고 연결된 1, 4, 5번 노드에서 방문 되지 않은 4, 5가 추가된다. 현재 큐는 8, 7, 4, 5. 출력은 '1 2 3 '.
4. 다음은 8번 노드가 빠지고 연결된 노드는 1, 7이다. 전부 방문했으니 아무일도 일어나지 않는다. 출력은 '1 2 3 8 '.
5. 7번 노드가 빠지고 이제 마지막 노드인 6번이 큐에 추가된다. 큐에 모든 노드가 추가되었고 결과적으로 출력은 '1 2 3 8 7 4 5 6 '.

---

미로 탈출

 

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

 

입력 조건

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

입력 예시

5 6
101010
111111
000001
111111
111111

 

출력 예시

10

---

접근

 일단 풀지못했다. 가장 큰 문제는 문제에서 bfs라고 알려주지 않았다면 dfs로 시도해버렸을 수도있다는것이다. 사실 dfs문제를 풀 때도 dfs문제라는 것을 제시했기 때문에 풀었다고 느꼈다. 문제에서 제시해주었으니 알아들었지, 알아들었어도 bfs식으로 구현을 하지 못했다.

 

구현(해설)

from collections import deque

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    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 < 0 or ny < 0 or nx >= n 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))

 

 (0, 0)좌표부터 시작한다. 첫 좌표를 큐에 넣고 이동 가능한 좌표의 값을 1씩 올리는 알고리즘인데, 결국에 dfs처럼 모든 인덱스를 방문하게 된다. 최종 목적지는 우하단으로 정해져있으므로 모든 지역을 방문하더라도 거리만 체크하면 풀어낼 수 있는 알고리즘으로 보인다.

---

마치며

 dfs/bfs를 알아보았는데 그래프나 트리구조 문제를 만난다면 탐색 알고리즘으로 인식하고 시도해 볼 수는 있을 것 같다. 중요도는 탐색 문제로 인식하는 것, dfs인지 bfs인지 적합한 알고리즘을 결정하는 것, 구현 등의 순서로 생각이 된다.

 

 결국 많이 경험하지 않고서는 알 수 없으니 꾸준히 노력해 보겠다.