BFS 너비 우선 탐색

froajnzd·2024년 1월 19일

algorithm

목록 보기

5/11

BFS (Breadth First Search)
너비 우선 탐색
맹목적 탐색 방법 중 하나
시작 정점 방문하고 찾고자 하는 값을 찾을 때까지 시작노드와 인접한 노드들을 우선 방문하는 방법

BFS의 특징

직관적이지 않다.
- 시작 노드를 기준으로 거리에 따라 단계별로 탐색하는 것이기 때문에 오해 발생 여지가 있다.

(DFS와 달리) 재귀적으로 동작하지 않는다.

반드시 그래프를 탐색하면서 어떤 노드를 방문했었는 지의 여부를 검사해야한다. (visited 변수)
- 무한루프에 빠질 위험이 있기 때문

시간복잡도
인접 행렬 : $O(|V|^2)$ ➡ |V|개의 노드에 대해 |V|개의 엣지 탐색
인접 그래프 : $O(|V|+|E|)$ ➡ |V|개의 노드와 |E|개의 엣지 탐색

📕 BFS를 사용해야하는 문제의 조건

트리 혹은 그래프 탐색 문제여야 한다.

💡 BFS의 장점

출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.

🥺 BFS의 단점

경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 많은 기억 공간을 필요로 하게 된다.

해가 존재하지 않는다면
유한 그래프(finite graph)의 경우 ➡ 모든 그래프를 탐색한 후에 실패로 끝난다.
무한 그래프(infinite graph)의 경우 ➡ 결코 해를 찾지도 못하고, 끝내지도 못한다.

📝 BFS를 사용하는 문제의 예

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때

최단 경로 찾기
가중치가 1이어야 한다
이 가중치가 문제에서 찾고자 하는 값이어야 한다. (ex. 최단 거리라면 가중치==거리, 최소 시간이라면 가중치==시간)
정점과 간선의 개수가 많지 않아야 한다.
➡ 시간복잡도가 $O(V+E)$ 이기 때문에 너무 많은 경우 시간 내에 해결이 안된다.

🎡 BFS를 응용하여 푸는 다른 알고리즘

Topological Algorithm 위상정렬 알고리즘 : 사이클이 없는(No Cycle) 방향 그래프(Directed Graph)
- 사이클이 있는지 없는지 탐지하기 위해서도 쓰임
최단 경로 찾기 및 minimum spanning tree
P2P 네트워크
Ford-Fulkerson Algorithm
Network Broadcasting
Garbage Collection
검색 엔진 Crawling
Social Networking
GPS 네비게이션 시스템

🎁 구현 방법

먼저 들어온 데이터를 먼저 탐색하는 방식(선입선출)이기 때문에, Queue를 사용하여 구현하는 것이 가장 바람직하다.

시작 노드의 자식들을 queue에 추가한다.
문제 조건 검색
그 다음 방문은 queue의 첫번째 노드이다.
방문한 노드를 visit 처리하고, queue에서 노드를 제거한다.
그 다음으로 인접한 노드에 방문하기 위해 2-4단계를 반복하여 조건에 맞는 노드를 찾은 경우 반복문을 빠져나온다.

c.f. 유사한 알고리즘

Prim Algorithm : 그리디 알고리즘에 근간을 두고 있다. 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택한다.
Dijkstra Algorithm

🏃‍ 예시 문제 1

<BAEKJOON: 실버 1> 단지번호붙이기

해답

visit을 처리하는 과정에서 중복 탐색하는 경우가 없도록 꼼꼼히 살펴보도록 한다.

import sys
input = sys.stdin.readline

N = int(input())
map = []
for _ in range(N):
    map.append(input().strip())

visit = [[0] * N for _ in range(N)]
group = []

def bfs_find_village(x, y):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    queue = []
    queue.append((x, y))
    visit[x][y] = 1
    house = 1
    while queue:
        a, b = queue.pop()
        # (a, b)의 앞뒤양옆에 집이 있으면 queue에 추가
        for i in range(4):
            ax, by = a+dx[i], b+dy[i]
            if 0 <= ax < N and 0 <= by < N \
                    and visit[ax][by] == 0 \
                    and map[ax][by] == '1':
                queue.append((ax, by))
                # (ax, by) 방문 처리, 집 수 +1
                visit[ax][by] = 1
                house += 1
    return house

for i in range(N):
    for j in range(N):
        # 이전에 방문하지 않은 집들만 방문한다
        if map[i][j] == '1' and not visit[i][j]:
            # 단지 내 집 개수를 추가한다
            # (i, j)와 인접한 집들을 찾아 visited 처리한다.
            group.append(bfs_find_village(i, j))

print(len(group))
group.sort()
for i in group:
    print(i)

🏃‍ 예시 문제 2

<BAEKJOON: 실버 1> 미로 탐색

해답

미로는 최소 거리로 도달해야 하므로 bfs를 써야한다는 것은 자명하다.
반복문을 3중이나 썼으니 queue의 세번째 변수에 거리 값을 추가하여 중간에 for문을 없애는 것도 좋아보인다.

import sys
input = sys.stdin.readline

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

N, M = map(int, input().split())
miro = []
for _ in range(N):
    miro.append(input().strip())

visit = [[0] * M for i in range(N)]
queue = []
queue.append((0, 0))
visit[0][0] = 1
move = 1
while queue:
    iter = len(queue)
    move += 1
    # depth를 기준으로 한 depth마다 for문을 새로 돌린다
    for i in range(iter):
        a, b = queue.pop(0)
        # (a,b)의 앞뒤양옆 길로 가본다
        for q in range(4):
            ax, by = a+dx[q], b+dy[q]
            # 구한 경우
            if ax == N-1 and by == M-1:
                print(move)
                exit(0)
            if 0 <= ax < N and 0 <= by < M \
                    and miro[ax][by] == '1' \
                    and not visit[ax][by]:
                queue.append((ax, by))
                visit[ax][by] = 1