DFS, BFS

DFS: 깊이 우선 탐색

• 현재 노드에서 연결된 곳들을 끝까지 탐색
• 경로의 특징이 중요한 문제
• 스택 또는 재귀함수를 이용

BFS: 너비 우선 탐색

• 현재 노드에 연결된 곳들을 우선적으로 탐색(단계별로)
• 최단거리를 구하는 문제
• 큐를 이용

문제풀이

문제 링크 - 백준 #2606 바이러스
아래 그림에서, 1과 연결된 노드들이 감염되며, 1번을 통해 감염된 노드의 수를 최종 출력하는 것이다. (1번 제외)

• DFS 진행 순서: 1 2 3 5 6
• BFS 진행 순서: 1 2 5 3 6

DFS

재귀함수 이용

1. 오류 발생

import sys

# DFS
def dfs(v):
    # 감염 노드 수 저장 객체
    global ift
    visit_list[v] = 1
    # 링크 모두 탐색
    for i in range(L):
        if graph[i][0] == v and visit_list[graph[i][1]] == 0:
            ift+=1
            dfs(graph[i][1])

# 초기화
N = int(sys.stdin.readline())
L = int(sys.stdin.readline())
graph = []
visit_list = [0] * (N+1)
global ift
ift = 0
for _ in range(L):
    graph.append(list(map(int, sys.stdin.readline().split())))

# 함수 호출
dfs(1)
print(ift)

• 원인: 링크 연결은 일방적인 것이 아님을 생각하지 못함
  예) 무조건 1->2로 감염시킬 수 있는 것은 아님. 5->2도 가능하다.
• 반례:

4
3
1 4
2 4
2 3

2. 노드 연결 양방향 정보를 전부 저장

import sys

# DFS
def dfs(v):
    global ift
    visit_list[v] = 1
    # 현재 노드와 연결된 지점 모두 방문
    for i in graph[v]:
        if visit_list[i] == 0:
            ift+=1
            dfs(i)

# 초기화
N = int(sys.stdin.readline())
L = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
visit_list = [0] * (N+1)
global ift
ift = 0
for _ in range(L):
    a, b = list(map(int, sys.stdin.readline().split()))
    # graph를 미리 초기화 후, 양방향의 정보를 저장
    graph[a].append(b)
    graph[b].append(a)

# 함수 호출
dfs(1)
print(ift)

스택 이용

import sys

# DFS
def dfs(v):
    global ift
    visit_list[v] = 1
    # 현재 노드와 연결된 지점 모두 방문
    s = [v]
    while s:
        n = s.pop()
        # 현재 노드에 연결된 노드를 차례로 저장하는데,
        # 다음 노드를 저장하기 전에 먼저 현재 노드의 자식 노드 저장을 수행
        for n_next in graph[n]:
            if not visit_list[n_next]:
                visit_list[n_next] = 1
                s.append(n_next)
                ift+=1

# 초기화
N = int(sys.stdin.readline())
L = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
visit_list = [0] * (N+1)
global ift
ift = 0
for _ in range(L):
    a, b = list(map(int, sys.stdin.readline().split()))
    # graph를 미리 초기화 후, 양방향의 정보를 저장
    graph[a].append(b)
    graph[b].append(a)

# 함수 호출
dfs(1)
print(ift)

현재 노드와 연결된 노드들이 계속해서 저장되는데, 하나의 자식 노드(쌍방향이지만 표현상)가 저장되면 그 자식 노드(n_next)들이 먼저 저장된다. 그렇기 때문에 스택에서 다음으로 처리할 노드는 직전에 추가된 자식 노드가 된다.

BFS

큐 이용

import sys
from collections import deque

# bfs
def bfs(v):
    global ift
    # Deque 사용
    q = deque([v])
    visit_list[v] = 1
    while q:
        n = q.popleft()
        for n_next in graph[n]:
            if not visit_list[n_next]:
                visit_list[n_next] = 1
                q.append(n_next)
                ift += 1

# 초기화
N = int(sys.stdin.readline())
L = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
visit_list = [0] * (N+1)
global ift
ift = 0
for _ in range(L):
    a, b = list(map(int, sys.stdin.readline().split()))
    # graph를 미리 초기화 후, 양방향의 정보를 저장
    graph[a].append(b)
    graph[b].append(a)

# 함수 호출
bfs(1)
print(ift)

Stack과 비슷한 원리인데, Queue를 사용하여 먼저 들어온 이전 층의 노드를 더 빨리 처리할 수 있게 한다.

Deque

• Stack과 Queue의 기능을 모두 가짐
• 계산 속도가 빨라서 사용

1. Stack 관련 기능

• append()
• pop()

2. Queue 관련 기능

• appendleft()
• popleft()

관련 문제

백준 DFS BFS 관련 문제