DFS, BFS

그래프 탐색 - DFS / BFS

1. 깊이 우선 탐색 (DFS)

시작 정점에서 탐색 가능한 최대 깊이의 정점까지 탐색하는 방법. 최대 깊이까지 도달했다면 방문한 정점들을 역순으로 재방문하며 탐색 가능한 정점이 있는지 확인한다. 탐색 가능한 정점이 있다면 해당 정점부터 다시 최대 깊이 정점까지 탐색을 진행한다. 스택 또는 재귀로 구현할 수 있다. 아래 그림의 그래프를 DFS로 탐색하는 과정은 다음과 같다. 

 

1. 1번 노드에서 탐색을 시작한다. 스택에 1번 노드를 삽입한다. ([1])
2. 1번에서 탐색 가능한 노드는 2번과 4번이 있다. 2번을 스택에 삽입한다. ([1, 2])
3. 2번에서 탐색 가능한 노드는 3번과 4번이 있다. 3번을 스택에 삽입한다.([1, 2, 3])
4. 3번에서 탐색 가능한 노드는 2번과 4번이 있다. 4번을 스택에 삽입한다. ([1, 2, 3, 4])
5. 4번에서 더이상 탐색 가능한 노드는 없으므로 최대 깊이에 도달했다고 할 수 있다. 스택에 있는 정점들을 역순으로 방문하며 탐색 가능한 정점이 있는지 확인한다. 
6. 스택에서 pop을 하면 4번이 나온다. 4번에서 탐색 가능한 노드는 없다. ([1, 2, 3])
7. pop을 하면 3번이 나온다. 탐색 가능한 노드는 없다. ([1, 2])
8. pop을 하면 2번이 나온다. 탐색 가능한 노드는 없다. ([1])
9. pop을 하면 1번이 나온다. 탐색 가능한 노드는 없다. ([])
10. 스택이 비었으므로 DFS를 종료한다. 

 

1) stack으로 DFS 구현하기

예시) 백준 24479번

# dfs - 스택
import sys
input = sys.stdin.readline

def dfs(idx):
    global cnt # 전역변수로 사용
    stack = [idx] # 스택
    while stack: # 스택이 비지 않았다면
        current = stack.pop() # 스택에 마지막에 들어온 값이 현재 노드
        if visited[current] != 0: # 만약 이미 방문한 적이 있다면 넘기기
            continue
        visited[current] = cnt # 방문하지 않은 노드라면 방문 순서 값 주기
        cnt += 1 # 순서 증가
        for i in graph[current]: # 연결된 노드만큼 반복
            if not visited[i]: # 아직 방문하지 않은 노드가 있다면 스택에 넣어주기 
                stack.append(i)

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)] # 1 ~ n까지 이차원배열 생성
visited = [0] * (n + 1) # 방문 여부를 표시할 배열 생성
cnt = 1 # 방문 순서

# 간선 만들기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b) # 양방향 간선
    graph[b].append(a)

# 내림차순 정렬. 스택은 마지막값부터 나오기때문에 역순으로 정렬해준다.
for i in range(n + 1):
    graph[i].sort(reverse=True)

dfs(r) # 시작정점부터 방문 시작

for i in range(1, n + 1): # 1번 노드부터
    print(visited[i])

 

2) 재귀로 DFS 구현하기

파이썬은 재귀 함수 최대 깊이에 대한 제한이 있다. (최대 1000)

더 깊은 재귀 깊이가 필요하다면 sys.setrecursionlimit을 통해 깊이를 늘려주어야 한다.

from sys import setrecursionlimit

setrecursionlimit(10 ** 6) # 더 많이 하면 메모리 초과할수도 있음 

# dfs - 재귀
import sys
sys.setrecursionlimit(10 ** 6) # 재귀 깊이 늘리기
input = sys.stdin.readline

def dfs(idx):
    global cnt # 전역변수로 사용
    visited[idx] = cnt # 방문한 노드 인덱스에 방문 순서를 넣어줌
    graph[idx].sort() # 오름차순 정렬

    for i in graph[idx]: # 그래프의 각 정점과 연결된 노드들을 방문.
        if visited[i] == 0: # 아직 방문하지 않은 노드라면
            cnt += 1 # 방문 순서 증가
            dfs(i) # 해당 노드 방문을 위해 함수 호출 

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)] # 1 ~ n까지 이차원배열 생성
visited = [0] * (n + 1) # 방문 여부를 표시할 배열 생성
cnt = 1 # 방문 순서

# 간선 만들기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b) # 양방향 간선
    graph[b].append(a)

dfs(r) # 시작정점부터 방문 시작

for i in range(1, n + 1): # 1번 노드부터 
    print(visited[i])

 

 

2. 너비 우선 탐색 (BFS)

탐색을 시작하는 정점에서 가까운 정점을 먼저 탐색하는 방식. 최단 경로 문제에서 주로 사용됨. 

먼저 발견한 정점과 인접한 정점들을 탐색하면서 큐에 삽입하는데, 이전에 방문한 정점인지 반드시 확인해야한다. 그렇지 않으면 이전에 방문한 정점을 큐에 삽입하면서 끊임없이 탐색을 반복하게 된다. 

아래 그림과 같은 그래프가 있다고 했을때 BFS로 탐색하는 과정은 다음과 같다. 

1. 1번 노드에서부터 탐색을 시작한다. 가까운 노드는 2번과 4번이 있다. 아직 방문하지 않았으니 2번, 4번 노드가 큐에 추가된다. ([2, 4])
2. 디큐를 하면 2번이 나온다. 가까운 노드는 1번, 3번, 4번이 있다. 1번은 이미 방문했으므로 3번과 4번이 큐에 추가된다. ([4, 3, 4])
3. 디큐를 하면 4번이 나온다. 4번과 가까운 노드는 1번, 2번, 3번이 있다. 1번과 2번은 이미 방문했으므로 3번이 큐에 추가된다. ([3, 4, 3])
4. 디큐를 하면 3번이 나온다. 3번과 가까운 노드는 2번, 4번이 있다. 모두 방문했으므로 큐에 추가하지 않는다. ([4, 3])
5. 디큐를 하면 4번이 나오지만 이미 방문했으므로 무시한다. ([3])
6. 디큐를 하면 3번이 나오지만 이미 방문했으므로 무시한다. ([])
7. 큐가 비었으므로 탐색을 종료한다. 

 

1) deque으로 BFS 구현하기

예시) 백준 24444번

from collections import deque
import sys
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)] # 1~n까지 만들어줌

for _ in range(m): # 그래프에 간선 추가
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [0] * (n + 1) # 방문 기록
visited[r] = 1 # 1부터 시작

queue = deque([r]) # 덱에 시작 정점 추가

cnt = 1 # 방문 순서
while queue: # 덱이 비어있지 않다면
    node = queue.popleft() # 덱의 0번째 요소
    graph[node].sort() # 오름차순 정렬
    
    for i in graph[node]: # 연결된 노드들을 모두 탐색
        if not visited[i]: # 아직 방문하지 않았다면
            queue.append(i) # 덱에 추가
            cnt += 1 # 방문순서 증가
            visited[i] = cnt # 방문 기록[인덱스]에 순서 갱신
            
for i in visited[1:]: # 1부터 n까지이니 1부터 슬라이싱해서 출력
    print(i)

 

 

 

 

 

----------

🥰 Liked (좋았던 점)

그동안 잘 이해하지 못했던 DFS와 BFS에 대해 다시 정리해보고 문제를 풀어보면서 이해할 수 있었다.

 

😢 Lacked (아쉬웠던 점)

아직은 코드 이해만 하고 있어서 혼자서 문제를 풀기가 조금 어려웠다. 그래도 한 65%정도는 완성 가능. 조금만 더 이해하고 문제를 파악하려고 노력하는게 좋을거같다. 

 

😮 Learned (배운 점)

DFS를 스택으로 구현하는 것과 BFS를 큐로 구현하는 것에 대해서 배울 수 있었다. 지난 시간에 스택과 큐를 배우고 나서 구현해보니 탐색 방식을 이해하는데 더 도움이 되었다. 

 

🤔 Longed for (앞으로 바라는 점)

아직 문제를 보고 DFS인지 BFS인지 파악하는게 조금 어렵다. 그리고 코드 구조를 다 익히지 못해서 조금 더 시간을 들여서 기초 문제들을 연습해봐야겠다.