[Algorithm] 그래프 탐색 - BFS / DFS

대표적인 문제 유형
1. 경로 탐색(최단 거리, 시간)
2. 네트워크 연결
3. 조합

[Python] 백준 1260번: DFS와 BFS

 

BFS(Breadth-First Search): 너비 우선 탐색

  그래프에서 가까운 노드부터 우선적으로 탐색한다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료 구조 Queue를 사용한다.

경로가 매우 길 경우에는 탐색 가지가 증가함에 따라 많은 메모리 공간을 필요로 한다. 해가 존재하지 않으면 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝난다. 무한 그래프의 경우 해를 찾지도 못하고 끝내지도 못한다.

1. 시작 노드을 Queue에 넣고 방문 처리한다.
2. Queue에서 노드를 꺼내고 인접 노드 중에 방문하지 않는 노드를 큐에 삽입한 뒤 방문 처리한다.
3. 2번 과정을 더 수행할 수 없을 때까지 반복한다.

 

🌿 구현하기

1. Queue에서 꺼내 온다. (Deque)
2. 목적지인가?
    2-1. 목적지라면 return
3. 연결 노드 순회
    3-1. 갈 수 있는가?
        3-1-1. 방문 체크
        3-1-2. Queue에 넣는다.

Queue에 쌓이는 데이터는 이후 방문할 곳을 의미한다.

from collections import deque

def bfs(x, y):
	
    queue = deque([(x, y)]) # 초기값
    
    while queue:
        k = queue.popleft()
        
        if 탐색 불가능 조건:
        	break

        if 주변 노드 값 비교 조건:
            # queue.append(주변 노드 A)
            # A의 값을 변경하여 방문 여부를 체크하거나 혹은 방문 횟수 설정

bfs(...) # 함수 안에서 while문을 사용하므로 한 번만 호출한다.

 

🌿 예제

1️⃣ 2차원 공간에서 최단 거리를 구하는 문제

각 노드에 방문할 때마다 방문 횟수를 기록한다.

def bfs():
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < N and 0 <= ny < M and box[nx][ny] == 0:
                box[nx][ny] = box[x][y] + 1
                queue.append([nx, ny])

bfs()

2️⃣ 특정 조건의 상태에 따라 별도의 벡터 상태를 기록해야 하는 문제

배열을 한 차원 더 만든다. (벽 부수기 문제)

 

DFS(Depth-First Search) : 깊이 우선 탐색

  그래프에서 깊은 부분을 우선적으로 탐색한다. 가장 깊은 노드까지 들어가고 더 이상 들어갈 수 없으면 그 이전 노드를 탐색한다. 모든 노드를 방문하고자 할 때나, 이동 과정에 제약이 있을 경우 선택한다. 탐색 시간이 BFS보다 느리다. 스택 자료 구조(혹은 재귀 함수)를 이용한다.

현 경로의 노드를 기억하기 때문에 적은 메모리를 사용한다. 찾으려는 노드가 깊은 단계일 경우 빠르다. 해가 없는 경우 단계가 끝날 때까지 탐색한다는 단점이 있으며, 효율성을 높이기 위해서는 미리 지정한 임의 깊이까지만 탐색하고, 발견하지 못하면 빠져나와서 다른 경로를 탐색하는 방법을 사용한다. DFS는 해에 도착하면 탐색을 종료하므로 얻어진 해가 최단 경로라는 보장이 없다.

1. 시작 노드를 스택에 넣고 방문 처리한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문 처리한다.
   방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 뺀다.
3. 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

🌿 구현하기

1. 목적지인가?
    1-1. 목적지라면 return
2. 연결 노드 순회
    2-1. 갈 수 있는가?
        2-1-1. dfs() 호출

DFS를 호출하면 Stack에 함수가 쌓인다. 이는 이미 방문한 곳을 뜻한다.

위의 주석을 작성하고 dfs 코드를 간단하게 구현해 본다. 전체를 다 순회했을 때 조건을 걸어서 삭제할 수 있는 부분은 삭제한다. 나머지 상세 구현을 하고, 메서드 분리가 가능하면 분리한다.

def dfs(...):
	
    if 탐색 종료 조건:
    	return False
    
    if 추가 탐색 가능 조건:
    
    	# 해당 위치에 방문했음을 기록 (선택)
        ...
        
        dfs(...) # 탐색 범위의 재귀 함수 동작
        
        return True # 끝까지 탐색을 마친 경우
    
    return False # 추가 탐색 조건에 맞지 않을 경우

for i in range(N):
    for j in range(M):
    	if dfs(i, j) == True:
     	   탐색 완료 시 동작 코드

import sys
sys.setrecursionlimit(10**6)

재귀 함수를 사용할 때 기본적인 재귀의 깊이를 넘어서면 RecursionError가 발생한다. (백준의 최대 재귀 깊이는 1000이다.) 이를 방지하기 위해서 sys 모듈의 setrecursionlimit()메서드로 제한 크기를 조절할 수 있다. 보통 10⁶ 혹은 10⁹으로 설정한다.

 

🌿 예제

# 방문 체크를 하여 탐색
def dfs(i):
    visited[i] = True
        
    # 인접한 노드 탐색
    for j in range(n):

        # 추가 탐색 가능 조건
        if not visited[j] and computers[i][j]:
            dfs(j)

# 탐색 종료 조건을 두어 탐색
def dfs(numbers, target, depth, node_sum):

    # 탐색 종료 조건
    if depth == len(numbers):
        if node_sum == target:
            nonlocal answer
            answer += 1
            
    # 추가 탐색 가능 조건
    else:
        dfs(numbers, target, depth + 1, node_sum + numbers[depth])
        dfs(numbers, target, depth + 1, node_sum - numbers[depth])
    
    return answer

# Connected Components
def dfs(x, y):
	
    # 탐색 종료 조건
    if x <= -1 or x >= n or y <= -1 or y >= m:
    	return False
    
    # 추가 탐색 가능 조건
    if graph[x][y] == 0:
    	graph[x][y] == 1 # 방문 체크
        
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        
        return True
    return False

 

🪴 문제 유형

1. 모든 정점을 방문해야 할 때: 둘 다 O
2. 경로의 특징을 저장해 둬야 할 때: DFS
3. 최단 거리를 구해야 할 때: BFS
4. 그래프의 규모가 정말 클 때: DFS
5. 그래프의 규모가 크지 않고, 시작 지점으로부터 대상이 멀지 않을 때: BFS
6. 두 가지 일이 동시에 벌어질 때: BFS

import sys
from collections import deque

input = sys.stdin.readline

N, M, V = map(int, input().split()) # 정점 개수, 간선 개수, 탐색 시작 정점

dfs_visited = [False] * (N + 1)
bfs_visited = [False] * (N + 1)

graph = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

def dfs(v):
    dfs_visited[v] = True
    print(v, end = " ")
    
    for i in range(1, N + 1):
        if not dfs_visited[i] and graph[v][i] == 1:
            dfs(i)

def bfs(v):
    bfs_visited[v] = True
    
    queue = deque()
    queue.append(v)
    
    while queue:
        popV = queue.popleft()
        print(popV, end = " ")
        
        for i in range(1, N + 1):
            if not bfs_visited[i] and graph[popV][i] == 1:
                queue.append(i)
                bfs_visited[i] = True
                
dfs(V)
print()
bfs(V)

 

🪴 각 노드의 연결 정보 정리

문제에서 노드의 연결 정보가 [ A, B ] 형태의 리스트로 제시된 경우 아래와 같이 저장할 수 있다.

6 5 # 정점의 개수와 간선의 개수
1 2
2 3
4 5
6 3
5 3

# graph = [list(map(int, input().split())) for _ in range(M)]
# [[1, 2], [2, 3], [4, 5], [6, 3], [5, 3]]

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort() # 더 빠른 탐색을 위해서 정렬
    graph[b].sort()

# [[],[2],[1, 3],[2, 5, 6],[5],[3, 4],[3]]