DFS(깊이 우선 탐색)

DFS(Depth First Search, 깊이 우선 탐색)은 그래프를 방문하거나 탐색하는 방법 중 하나이다. DFS는 주로 완전 탐색이나 백트래킹과 같이 탐색의 횟수, 즉 그래프의 최대 경로가 정해져 있거나 예측 가능한 경우에 이용한다. 

 

DFS는 선택한 정점을 저장하기 위한 도구로 큐 대신 스택을 이용한다는 점에서 BFS와 차이를 보인다. 다만 스택을 직접 사용하지 않고, 그 원리를 이용하는 재귀 함수를 통해 구현하는 편이다.

 

def dfs(start):
	if(visited[start]): 
    	return
    visited[start] = True
    for node in adj[start]:
        if not visited[node]:
            dfs(node)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
start_node = input('시작 노드를 입력하세요 : ')

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


dfs(start_node)

다음 코드는 백준 11724번 풀이에서 가져와 약간 변형한 코드이다. 다만 보통 재귀 함수를 사용하는 경우 런타임 에러가 나는 경우가 잦아 다음의 코드를 통해 그 횟수를 직접 지정해주는 경우가 많다. 

 

import sys
sys.setrecursionlimit(10000)