DFS/BFS

DFS(Depth-First-Search)

깊이 우선 탐색
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
스택 자료구조를 이용하여 구현

동작과정

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

소스코드

# DFS

# 재귀이기 때문에 재귀제한을 풀어줘야함
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline		# 여러개의 input 받을때 시간 단축

# 방문 정보를 리스트 자료형으로 표현
visited = [False] * 9

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
	[],					# 1번 노드와 연결된 노드들
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]

def DFS(graph, v, visited):
	visited[v] = True	# 현재 노드를 방문 처리
    print(v, end = ' ')
    
    for i in graph[v]:
    	if not visited[i]:	# visited[i]==False이면
    		DFS(graph, i, visited)
# 현재 노드와 연결된 다른 노드를 재귀적으로 방문

DFS(graph, 1, visited)

→ 1 2 7 6 8 3 4 5

BFS(Breadth-First-Search)

너비 우선 탐색 이라고 부르며, 가까운 노드부터 탐색하는 알고리즘
가장 가까운 노드부터 우선 순위를 가져야 하기에, 큐(queue)를 이용하여 구현할 수 있다.
일반적으로 DFS보다 수행 시간이 좋은 편

동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복

소스코드

from collections import deque
# 방문 정보를 리스트 자료형으로 표현
visited = [False] * 9

# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
	[],					# 1번 노드와 연결된 노드들
	[2, 3, 8],
	[1, 7],
	[1, 4, 5],
	[3, 5],
	[3, 4],
	[7],
	[2, 6, 8],
	[1, 7]
]
def BFS(graph, v, visited):
	queue = deque([v])
    
    # 현재 노드 방문 처리
    visited[v] = True
    
    # 큐가 빌 때까지 반복
    while queue:
    	# 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end = ' ')
        
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
                
BFS(graph, 1, visited)

→ 1 2 3 8 7 4 5 6