새싹프로그래머의 이야기

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. DFS란? 

그래프를 탐색하는 알고리즘의 한 종류로, leaf node(자식이 없는 노드)에 도달할 때까지 한 방향으로 탐색하는 기법입니다.

*시간 복잡도는 인접리스트 방식의 DFS는 모든 노드(n)와 모든 간선(e)을 탐색했다고 할 수 있으므로, O(n+e)의 복잡도를 가집니다.

구체적으로 보자면, 다음과 같은 탐색과정을 거칩니다.

2. 코드 구현

• 재귀적 구현을 통하여 구현합니다.
• visited 배열을 통해 방문 여부를 확인하여야 합니다.
• 노드를 방문할 경우 방문처리를 해주며, 방문하지 않은 노드만 방문합니다.
• 방문하는 방향으로 leaf node에 도달할 때 까지 탐색을 진행합니다.
• 위, 과정을 모든 leaf node를 방문할 때 까지 반복합니다.

백준 알고리즘 1260번을 통하여 구현한 코드입니다.(https://www.acmicpc.net/problem/1260)

import sys
from collections import deque

n,m,v = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

for i in range(1,n+1):
    graph[i].sort()

visited_dfs = [False]*(n+1)

def dfs(n):
    print(n, end=' ')
    visited_dfs[n] = True

    for node in graph[n]:
        if visited_dfs[node]:
            continue
        dfs(node)
dfs(v)