#19 완전 탐색 - BFS(Breadth First Search)

1. BFS(Breadth First Search)

 BFS는 시작노드의 인접노드를 모두 방문한 뒤, 그 인접 노드들의 인접노드를 모두 방문하는 형태로 탐색해나가는 방식의 완전 탐색 알고리즘이다. 방문 순서를 그림으로 나타낸다면 다음과 같다.

 

위와 같이 트리를 방문할 경우 방문 순서는 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 이 된다.

 

DFS의 경우 재귀호출로 인접노드를 순차적으로 방문하면 자연스럽게 구현되는 형태였지만 BFS의 경우 직접 큐를 사용하여 구현해줘야 한다.  시간복잡도의 경우 DFS와 마찬가지로 인접리스트 구현이라면 O(|V|+|E|), 인접행렬 구현이라면 O(V^2) 가 된다.  BFS는 일반적으로 두 노드 사이의 최단거리를 구하는 문제나 인접노드에 대한 영향이 퍼져나가는 조건이 주어졌을 때 그 영향이 특정 수준에 도달하는데 걸리는 시간 등을 알아내는 문제 등에 주로 응용된다.

 

2. 최단거리 탐색

 시작 노드 기준으로 같은 레벨의 노드들을 탐색하는 것을 한 사이클이라 하면 BFS가 어떤 노드를 방문한 시점의 사이클 수가 그 노드까지의 최단거리가 된다. 다만 이 방법으로 최단거리를 찾을 수 있는 것은 가중치가 없거나 모두 같은 그래프인 경우 뿐이다. 가중치가 있는 그래프의 최단거리를 찾기 위해서는 Dijkstra's Algorithm이나 Bellman-Ford's Algorithm, Floyd-Warshall Algorithm 등을 사용해야 한다.  이 방법을 통해 가중치가 없는 그래프의 최단거리 문제(https://www.acmicpc.net/problem/2178)를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol2178():
    n, m = map(int, input().split())
    # 미로
    laby = [list(input().rstrip()) for _ in range(n)]
    
    # 시작 위치
    q = [(0, 0)]
    
    # 사이클 수
    cnt = 1
    
    while q:
        nq = []
        for r, c in q:
        	# 현재 위치가 이미 방문된 상태일 경우 continue
            if laby[r][c] != '1':
                continue
                
            # 현재 시점의 사이클 수 = 최단거리 로 갱신
            laby[r][c] = cnt
            
            # 인접 위치중 아직 방문하지 않았으며 갈 수 있는 위치를 큐에 삽입
            for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                if 0<=nr<n and 0<=nc<m and laby[nr][nc]=='1':
                    nq.append((nr, nc))
                    
        # 다음 사이클을 위한 큐로 교체
        q = nq
        
        # 사이클 수 증가
        cnt += 1
        
    # n, m까지의 최단거리 반환 (인덱스가 0부터 시작하도록 구현했기에 n-1, m-1)    
    return laby[n-1][m-1]

queue 나 deque 모듈을 사용하여 실제로 큐를 사용한 구현도 가능하지만 같은 레벨의 노드를 방문하는 사이클을 구분하고 싶을 경우 위와 같이 별도의 큐에 다음 방문 노드들을 삽입한 뒤 큐를 교체하는 방식도 사용할 수 있다. 

 

 

3. 상태 전이

 어떠한 상태가 한 노드로부터 인접 노드로 일정 시간이 지날 때 마다 전이가 된다는 전제가 주어졌을 경우,  얼마만큼의 시간이 지나야 전이가 특정 수준까지 도달하는지 알아내는 문제를 해결하는 데에도 BFS를 사용할 수 있다.  사실 말이 바뀌었을 뿐 결국 최단거리 문제와 같은 이치이기 때문에 문제만 제대로 이해한다면 쉽게 해결 가능하다. 관련 문제(https://www.acmicpc.net/problem/7576)를 BFS로 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol7576():
    m, n = map(int, input().split())
    # 토마토 상태
    tomato = [input().split() for _ in range(n)]
    
    # BFS 큐
    q = []
    
    # 익지 않은 토마토 수
    tc = 0
    
    for i in range(n):
        for j in range(m):
        	# 익지 않은 토마토가 있다면 익지 않은 토마토 갯수 증가
            if tomato[i][j] == '0':
                tc += 1
            # 익은 토마토가 있다면 좌표를 BFS 큐에 삽입
            elif tomato[i][j] == '1':
                q.append((i, j))
        
    # 익지않은 토마토가 없다면 0을 반환 - 이미 다 익어있음
    if tc == 0:
        return 0
    
    # 익는데 필요한 날짜
    res = 0
    
    while q:
        nq = []
        for r, c in q:
        	# 익은 토마토에 인접한 토마토 중 익지 않은것이 있는 경우
            # 토마토를 익히고 익지 않은 토마토 수를 감소시킨다
            # 만약 익지 않은 토마토의 갯수가 0이된다면 지난 일수 res에 당일을 포함하여 res+1 반환
            # 익은 토마토의 좌표를 큐에 삽입
            for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                if 0<=nr<n and 0<=nc<m and tomato[nr][nc]=='0':
                    tomato[nr][nc] = '1'
                    tc -= 1
                    if tc == 0:
                        return res+1
                    nq.append((nr, nc))
        # 큐 교체
        q = nq
        
        # 일수 + 1
        res += 1
        
    # 큐를 빠져나올 때 까지 익지 않은 토마토 수가 0이 되지 않았다면 
    # 모든 토마토를 익힐 수 없는 배치이기 때문에 -1 반환
    return -1

위에서도 언급했지만 문제의 형태는 바뀌었지만 사실상 최단거리문제와 다를바가 없다.   다른 점이라면 시작 위치가 한 군데가 아니라는 것 정도이다. 시작부터 이미 전이가 완료된 상태이거나 전이가 완료될 수 없는 케이스인 경우의 예외처리를 잊지않고, 전이가 완료됐으면 바로 답을 반환하여 쓸데없는 추가연산을 하지 않도록 신경 써준다면 큰 어려움 없이 해결 가능한 문제이다.

 

DFS와 BFS는 처음에도 말했듯 코딩 테스트에서 굉장히 자주 사용하게 되는 알고리즘이고 결국 같은 완전탐색 알고리즘이지만 어느 한쪽으로는 해결이 불가능하거나 비효율적인 해결책이 되는 경우가 있기 때문에 두 방식 모두 잘 알아두고 여러 문제를 풀어보며 더 적합한 쪽을 골라 사용하는 습관을 들일 필요가 있다.