[알고리즘] 01. DFS & BFS

---

 

사담 공간

내가 제일 어려워하는 파트... 코테 전까지 문제도 많이 풀어봐야겠다

포스팅 순서는 그냥 코테 자주 출제되고 내가 잘 못푸는 순서대로.. 

 

---

키워드

 

#DFS #BFS #최단경로

 

---

1. DFS (Depth-First Search)

 

깊은 부분을 우선적으로 탐색하는 알고리즘

좀 더 자세히 풀어서 설명하면, 정점 v의 모든 간선이 조사된 후 v를 발견하게 해준 정점으로부터 나오는 간선을 조사하기 위해 뒤로 되돌아간다.

발견되지 않은 정점이 하나라도 남아 있으면 그 중 하나를 새 출발점으로 선택하고, 해당 출발점으로부터의 검색을 모든 정점을 방문하기 전까지 반복한다.

즉, 시작 지점으로부터 가장 멀리 있는 노드부터 탐색하게 된다.

 

동작 과정

1. 탐색 시작 노드를 스택에 삽입 후 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택 push 후 방문 처리
3. 방문하지 않은 인접 노드가 없다면 스택에서 pop
4. 2-3번 과정을 스택이 모두 빌 때까지 수행한다.

 

예시를 통해 직접 살펴보자.

 

[그림 1] 예시 그래프

그림에 나와있는 그래프를 노드 번호가 낮은 순으로 탐색하며, 노드 1에서 탐색을 시작한다.

 

탐색 과정

• 시작점인 노드 1을 스택에 넣고 방문처리 한다
  • visited = [1]
  • stack = [1]
• (1의 인접 노드) 방문하지 않은 노드 2를 스택 push, 방문 처리
  • visited = [1 2]
  • stack = [1 2]
• (2의 인접 노드) 방문하지 않은 노드 7을 스택 push, 방문 처리
  • visited = [1 2 7]
  • stack = [1 2 7]
• (7의 인접 노드) 방문하지 않은 노드 6을 스택 push, 방문 처리
  • visited = [1 2 7 6]
  • stack = [1 2 7 6]
• 노드 6에서 방문하지 않은 인접노드가 없다. 스택에서 pop
  • visited = [1 2 7 6]
  • stack = [1 2 7]
• (7의 인접 노드) 방문하지 않은 노드 8을 스택 push, 방문 처리
  • visited = [1 2 7 6 8]
  • stack = [1 2 7 8]
• 노드 8에서 방문하지 않은 인접 노드가 없다. 스택에서 pop
  • visited = [1 2 7 6 8]
  • stack = [1 2 7]
• 노드 7에서 방문하지 않은 인접 노드가 없다. 스택에서 pop
  • visited = [1 2 7 6 8]
  • stack = [1 2]
• 노드 2에서 방문하지 않은 인접 노드가 없다. 스택에서 pop
  • visited = [1 2 7 6 8]
  • stack = [1]
• (1의 인접 노드) 방문하지 않은 노드 3을 스택 push, 방문 처리
  • visited = [1 2 7 6 8 3]
  • stack = [1 3]
• (3의 인접 노드) 방문하지 않은 노드 4를 스택 push, 방문 처리
  • visited = [1 2 7 6 8 3 4]
  • stack = [1 3 4]
• (4의 인접 노드) 방문하지 않은 노드 5를 스택 push, 방문 처리
  • visited = [1 2 7 6 8 3 4 5]
  • stack = [1 3 4 5]
• 노드 5에서 방문하지 않은 인접 노드가 없다. 스택에서 pop
  • visited = [1 2 7 6 8 3 4 5]
  • stack = [1 3 4]
• 노드 4에서 방문하지 않은 인접 노드가 없다. 스택에서 pop
  • visited = [1 2 7 6 8 3 4 5]
  • stack = [1 3]
• 노드 3에서 방문하지 않은 인접 노드가 없다. 스택에서 pop
  • visited = [1 2 7 6 8 3 4 5]
  • stack = [1]
• 노드 1에서 방문하지 않은 인접 노드가 없다. 스택에서 pop
  • visited = [1 2 7 6 8 3 4 5]
  • stack = []
• 스택이 비었으므로 함수를 종료하고 결과값을 반환한다.

 

파이썬에서의 구현

위의 동작 과정을 토대로 스택을 사용하여 구현해보자.

# 덱 자료구조로 구현
from collections import deque

def dfs_by_deque(graph, start_node):
    # 스택과 방문 노드 지정
    stack = deque(); visited = deque()
    # 시작 노드 삽입
    stack.append(start_node)
    visited.append(start_node)
	
    # 스택이 빌 때까지
    while stack:
        node = stack.pop()
        # 방문하지 않은 인접 노드 있을 경우 스택에 추가 및 해당 노드 방문 처리
        if node not in visited:
            visited.append(node)
            stack.append(graph[node])
    return visited

visited 배열도 위 방식처럼 그냥 추가하는 경우와 1차원 boolean 리스트로 표현하는 방식이 존재한다.

개인적으로는 저게 더 좋은듯..

 

스택을 사용하는 알고리즘이므로 재귀 함수로도 표현이 가능하다.

# 재귀로 구현
def dfs_recursive(graph, start_node, visited):
    # 방문 노드에 추가
    visited.append(start_node)

    # 노드 시작지점부터
    for node in graph[start_node]:
        # 방문 안한 노드일 경우
        if node not in visited:
            # 노드 바꿔서 재귀호출
            dfs_recursive(graph, node, visited)
    
    return visited​

 

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

from dfs_deque import dfs_by_deque
print(dfs_by_deque(graph, 'A'))

from dfs_recursive import dfs_recursive
print(dfs_recursive(graph, 'A', []))

 

[그림 2] DFS 실행 결과

 

---

 

 

2. BFS (Breadth-First Search)

너비를 우선적으로 탐색하는 알고리즘

DFS는 최대한 멀리 있는 노드 (깊이 있는 노드) 를 우선으로 탐색했다면 BFS는 인접한 노드를 우선적으로 탐색하는 방식이다.

인접 노드를 반복적으로 FIFO 자료구조인 큐에 넣으면 먼저 들어온 것이 먼저 나가게 되고, 자연스럽게 가까이 있는 노드를 우선적으로 탐색하게 된다.

 

[그림 3] 예시 그래프

 

동작 과정

그림에 나와있는 그래프를 노드 번호가 낮은 순으로 탐색하며, 노드 1에서 탐색을 시작한다.

 

탐색 과정

• 시작점인 노드 1을 enqueue한 후 방문처리
  • visited = [1]
  • queue = [1]
• 노드 1 dequeue, 방문하지 않은 노드 1의 근접노드를 모두 enqueue한 후 방문처리
  • visited = [1 2 3 8]
  • queue = [2 3 8]
• 노드 2 dequeue, 방문하지 않은 노드 2의 근접노드를 모두 enqueue한 후 방문처리
  • visited = [1 2 3 8 7]
  • queue = [3 8 7]
• 노드 3 dequeue, 방문하지 않은 노드 3의 근접노드를 모두 enqueue한 후 방문처리
  
  • visited = [1 2 3 8 7 4 5]
  • queue = [8 7 4 5]
• 노드 8 dequeue, 방문하지 않은 노드 8의 근접노드를 모두 enqueue한 후 방문처리
  
  • visited = [1 2 3 8 7 4 5]
  • queue = [7 4 5]
• 노드 7 dequeue, 방문하지 않은 노드 7의 근접노드를 모두 enqueue한 후 방문처리
  
  • visited = [1 2 3 8 7 4 5 6]
  • queue = [4 5 6]
• 노드 4 dequeue, 방문하지 않은 노드 4의 근접노드를 모두 enqueue한 후 방문처리
  
  • visited = [1 2 3 8 7 4 5 6]
  • queue = [5 6]
• 노드 5 dequeue, 방문하지 않은 노드 5의 근접노드를 모두 enqueue한 후 방문처리
  
  • visited = [1 2 3 8 7 4 5 6]
  • queue = [6]
• 노드 6 dequeue, 방문하지 않은 노드 6의 근접노드를 모두 enqueue한 후 방문처리
  
  • visited = [1 2 3 8 7 4 5 6]
  • queue = []
• 큐가 비었으므로 함수를 종료하고 결과값을 반환한다.

 

파이썬에서의 구현

# 덱 자료구조를 통해 구현
from collections import deque

def bfs(graph, start_node):
    queue = deque(); visited = deque()
    
    # 시작 노드 큐에 넣고 시작
    queue.append(start_node)
    visited.append(start_node)
	
    # 큐가 빌 때까지
    while queue:
        # 큐에서 노드 하나 꺼내기
        node = queue.popleft()
		print(node, end=' ')
        
        # 인접 노드 순회
        for i in graph[node]:
            # 방문 노드 목록에 없을 경우
            if i not in visited:
				queue.append(i)
                visited.append(node)
    
    return visited

 

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

bfs(graph, 'A')

[그림 4] BFS 실행 결과

 

---

3. 코딩테스트 빈출 유형 & 관련 문제

1. 그래프의 모든 정점을 방문 후 경로를 출력하는 문제 : DFS, BFS 등 원하는 방식 사용
2. 경로의 특징을 저장해야 하는 문제 (ex. 경로에 같은 숫자가 있으면 안되는 경우 등) : DFS
3. 최단 거리 : BFS..라고는 하는데 DFS 풀이도 가능하다

 

DFS & BFS 관련 문제와 이를 베이스로 한 최단경로 알고리즘 (다익스트라, 플로이드-워셜) 은 다음 번 포스팅에서 다루도록 하겠다.