깊이 우선 탐색/너비 우선 탐색

깊이 우선 탐색과 너비 우선 탐색이란?

• 트리, 그래프를 탐색하는 두 가지의 알고리즘.
• 쉽게 설명하자면 미로 찾기.

          S
        /   \
       A     B
      / \     \
     C   D     E
          \      \
         F(출구)   G

• S에서 시작해서 F에서 탈출하는 미로가 있다고 할 때 (단, 낮은 순번부터 탐색한다고 가정)
  • DFS: S - A - C - D - F(출구)
    • C에서 이동할 곳이 없으므로 다시 A로 복귀
  • BFS: S - A - B - C - D - E - F(출구)
    • A, B를 탐색 후 다음 단계 탐색
    • C, D, E를 탐색 후 다음 단계 탐색

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

• 현재 위치에서 가장 깊은 곳 까지 탐색한 뒤 탐색이 종료되면 되돌아가서 다른 경로를 탐색하는 방식.
• 스택, 재귀 함수를 사용하여 구현한다.
• 메모리가 제한 적인 경우 BFS보다 유리

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

• 현재 위치에서 인접한 모든 위치를 방문하고 그 다음 레벨의 위치들을 순서대로 방문하는 탐색 방식
• 큐를 사용하여 구현한다.
• 최단 경로를 구하는 경우에 DFS보다 유리

 

예시 문제 - DFS와 BFS

https://www.acmicpc.net/problem/1260

설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

• 그래프 작성

# 입력 예시

5 5 3
5 4
5 2
1 2
3 4
3 1

n, m, start = map(int, input().split())
# n: 노드의 수 (5)
# m: 간선의 수 (5)
# start: 시작 노드 (3)

# 노드의 번호를 key로, 연결된 다른 노드들의 list를 value로 하여 dictionary형태로 graph를 정의
graph = {i: [] for i in range(1, n + 1)}

# 입력값(간선)을 순회하여 graph 완성
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
 
 # graph의 각 value를 정렬하여 작은 순번부터 방문하도록 함.
 for key in graph :
    graph[key].sort()

# graph == {1: [2, 3], 2: [1, 5], 3: [1, 4], 4: [3, 5], 5: [2, 4]}

 

예시 그래프의 형태

• DFS 탐색

DFS 탐색

• 3번 노드에서 시작하여 연결된 노드 중 숫자가 더 낮은 1번 노드를 탐색
• 1번 노드와 연결된 2번 노드를 탐색
• 2번 노드와 연결된 5번 노드를 탐색
• 5번 노드와 연결된 4번 노드를 탐색
• 탐색 종료
• 방문 순서: 3 1 2 5 4

 

• BFS 탐색

BFS 탐색

• 3번 노드에서 시작하여 연결된 노드 중 숫자가 더 낮은 1번 노드를 탐색
• 3번 노드로 돌아와서 연결된 노드인 4번 노드를 탐색
• 3번 노드와 연결된 노드를 모두 탐색 했으므로 1번노드와 연결된 2번 노드를 탐색
• 1번 노드와 연결된 노드를 모두 탐색했으므로 4번 노드와 연결된 5번 노드를 탐색
• 탐색 종료
• 방문 순서: 3 1 4 2 5

 

어떻게 구현을 할까?

DFS는 재귀 함수를, BFS는 큐를 사용하면 된다!

 

• DFS

def dfs(graph, n, start, result=None):
    if result is None:
        result = []
        
# graph: 탐색할 그래프
# n: 탐색할 노드의 수
# start: 시작 노드
# result: 탐색 결과를 추적하여 반환할 변수

def dfs(graph, n, start, result=None):
    if result is None:
        result = []
    
    result.append(start)
    
# result에 시작 노드를 추가하여 탐색을 했다는 것을 표시

def dfs(graph, n, start, result=None):
    if result is None:
        result = []
    
    result.append(start)
    
    if len(result) >= n or start not in graph:
        return result
        
# 종료 조건 설정
# len(result) >= n: 모든 노드를 탐색한 경우
# start not in graph: 현재 탐색 중인 노드가 존재하지 않는 경우

def dfs(graph, n, start, result=None):
    if result is None:
        result = []
    
    result.append(start)
    
    if len(result) >= n or start not in graph:
        return result
    
    # graph == {1: [2, 3], 2: [1, 5], 3: [1, 4], 4: [3, 5], 5: [2, 4]}
    
    for node in graph[start]:
        if node not in result:
            dfs(graph, n, node, result)
            if len(result) >= n:
                break
    
    return result
    
# for node in graph[start]: - 현재 노드에 연결된 모든 노드를 순회한다.
# if node not in result - 만약 노드가 result에 추가되어 있지 않은 경우에 (즉, 아직 방문하지 않은 노드의 경우) 다음 단계로 이동
# dfs(graph, n, node, result) -  아직 방문하지 않은 노드에 대하여 탐색 수행
# if len(result) >= n: break - 모든 노드를 탐색한 경우에는 즉시 탐색을 종료

• DFS의 탐색 순서
  • 3번 노드(시작점)/인접 노드[1, 4]
    • 1번 노드/인접 노드[2, 3]
      • 2번 노드/인접 노드[1, 5]
        • 5번 노드/인접 노드[2, 4
          • 4번 노드/인접 노드[5, 3] → 방문하지 않은 인접 노드가 없으므로 탐색 종료

 

• BFS

def bfs(graph, n, start):
    visited = []
    queue = [start]

# graph: 탐색할 그래프
# n: 탐색할 노드의 수
# start: 시작 노드
# queue라는 리스트에 시작 노드를 추가하고 탐색 시작

def bfs(graph, n, start):
    visited = []
    queue = [start]
    
    while queue:
        node = queue.pop(0)
        
# while queue: - queue의 원소가 존재하는 동안 반복 수행 (즉, 탐색할 공간이 남아있는 동안 계속 탐색)
# node = queue.pop(0) - 가장 앞에 있는 원소(다음으로 탐색할 노드)를 queue에서 제거하여 탐색 준비

def bfs(graph, n, start):
    visited = []
    queue = [start]
    
    while queue:
        node = queue.pop(0)
        
        if node not in visited:
            visited.append(node)
            
# 탐색할 노드(node)가 아직 방문하지 않은 노드일 경우(visited에 입력이 되지 않은 경우) visited에 해당 노드를 추가.

def bfs(graph, n, start):
    visited = []
    queue = [start]
    
    while queue:
        node = queue.pop(0)
        
       # graph == {1: [2, 3], 2: [1, 5], 3: [1, 4], 4: [3, 5], 5: [2, 4]}
     
        if node not in visited:
            visited.append(node)
            
            for neighbor in graph[node]:
                if neighbor not in visited and neighbor not in queue:
                    queue.append(neighbor)
    
    return visited

# node와 연결된 모든 인접 노드(neighbor)를 확인하여 다음 조건을 충족하는 경우 queue에 추가하여 반복 탐색
# neighbor not in visited - 인접 노드를 아직 방문하지 않은 경우
# neighbor not in queue - 인접 노드가 queue에 없는 경우(즉, 탐색 예정이 아닌 경우)

• BFS의 탐색 순서
  • 초기 상태
    • 시작 노드를 탐색 큐에 추가하여 탐색 시작
    • 큐: [3]
    • 방문: []
  • • 1단계
      • 3번 노드를 방문하고 연결된 노드들을 탐색 큐에 추가
      • 큐: [1, 4]
      • 방문: [3]
    • 2단계
      • 1번 노드를 방문하고 연결된 노드들을 탐색 큐에 추가
      • 큐: [4, 2]
      • 방문: [3, 1]
    • 3단계
      • 4번 노드를 방문하고 연결된 노드들을 탐색 큐에 추가
      • 큐: [2, 5]
      • 방문: [3, 1, 4]
    • 4단계
      • 2번 노드를 방문하고 연결된 노드들을 탐색 큐에 추가 → 이미 모든 노드를 방문 했거나 탐색 큐에 있으므로 추가하지 않음
      • 큐: [5]
      • 방문: [3, 1, 4, 2]
    • 5단계
      • 5번 노드를 방문하고 탐색 큐가 비었으므로 탐색 종료
      • 큐: []
      • 방문: [3, 1, 4, 2, 5]