썸네일 출처: SK텔레콤

DFS/BFS

그래프를 탐색하기 위한 대표적인 알고리즘

스택과 큐

스택 (박스 쌓기)

선입후출 또는 후입선출 구조로 파이썬에서는 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()랑 pop()이 각각 맨 마지막에서 원소를 추가하고 삭제하기 때문.

큐 (대기 줄)

선입선출 구조. 파이썬에서는 collections.deque를 활용해서 popleft()로 맨 앞의 원소를 뽑아내는 방식으로 구현하면 된다.

재귀 함수

자기 자신을 다시 호출하는 함수. 내부적으로는 스택 구조로 실행된다. 자기 자신을 계속해서 호출하는 과정에서 가장 마지막에 호출된 함수가 종료되는 순간 그 앞의 함수가 수행된다. 그래서 재귀 함수를 사용할 때는 반드시 종료 조건을 명시해야 한다.

def function(args):
	function(args)

DFS; 깊이 우선 탐색

그래프에서 가장 깊은 부분부터 탐색하는 알고리즘.

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

스택을 이용하기 때문에 재귀 함수를 사용해서 구현하는 것이 좋다. 그 이유는? 간결하니까.

• 별도의 스택을 만들어서 거기에 넣는게 아님
• 스택에 인접 노드를 넣는 행위 == 재귀 함수를 통해 함수를 호출하는 행위
• '최상단 노드를 꺼낸다' == '재귀 함수가 종료된다'

# DFS 템플릿
def dfs(graph, v, visited):
	# 현재 노드 방문 처리
    visited[v] = True
    
    ##### 노드를 방문해서 해야 하는 연산 #####
    print(v)
    
    # 현재 노드와 인접한 노드를 스택에 넣는다 == 재귀적으로 방문
    for i in graph[v]: # graph[v]: 현재 노드 v와 인접한 노드들
    	if not visited[i]:
        	dfs(graph, i, visited)

graph = [[...],
		 [...],
         ...]
         
visited = [False] * n

dfs(graph, 1, visited)

단, DFS를 통해 탐색한 해는 최적을 보장하지는 않는다.

BFS; 너비 우선 탐색

가까운 노드부터 탐색하는 알고리즘.

0. 시작 노드를 큐에 넣고 방문 처리를 한다.
1. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 몽땅 큐에 넣고 방문 처리를 한다.
2. 1번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

큐를 이용하기 때문에 collections.deque를 사용해서 구현하면 된다.

# BFS 템플릿
from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    # 현재 노드 방문 처리
    visited[start] = True
    
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 노드 꺼내기
    	v = queue.popleft()
        ##### 노드를 방문해서 해야하는 연산 ######
        print(v)
        
        # 꺼낸 노드의 인접 노드 중 방문하지 않은 노드를 큐에 넣고 방문 처리
        for i in graph[v]:
        	if not visited[v]:
            	queue.append(i)
                visited[i] = True

graph = [[...],
		 [...],
         ...]

visited = [False] * n

bfs(graph, 1, visited)