[데이터 구조와 활용] 깊이 우선 탐색 DFS

1. 깊이 우선 탐색 (DFS) 개요

- 그래프 탐색 방법 중 하나로 이름 그대로 그래프의 한 방향을 최대한 깊게 탐색한 후 더 이상 탐색할 곳이 없으면 다시 돌아와서 다른 방향을 탐색하는 방식

- 이 방식은 우리가 흔히 미로를 탐색할 때 한 방향으로 쭉 들어가다 막히면 다시 돌아오는 방식과 유사

(1) 탐색 원리와 스택

- DFS는 재귀를 통해 구현되지만 개념적으로는 스택의 동작방식(후입선출)과 관련되어 있음

- 가장 최근에 방문한 정점부터 탐색한다는 점에서 스택의 특성과 일치함

(2) 실제 DFS 구현에서는 왜 재귀를 활용할까?

- 실제로는 스택을 따로 구현하지 않고 재귀 호출을 이용하여 DFS를 구현하는 경우가 일반적임

- 재귀 호출 시 컴퓨터의 내부 호출을 자연스럽게 사용하여 코드가 더 직관적임

- 재귀로 구현하면 스택을 명시적으로 사용하지 않아도 내부적으로 스택의 기능을 그대로 활용 가능

(3) DFS 활용 사례

- 미로 찾기 게임, 그래프의 연결된 요소 찾기

2. 깊이 우선 탐색 (DFS) 구현

- 재귀를 이용한 방법, 스택을 명시적으로 이용한 방법

g = {     'A' : ['B','C','D'],     'B' : ['A','E'],     'C' : ['A','F'],     'D' : ['A','G'],     'E' : ['B','F'],     'F' : ['C','E'],     'G' : ['D']     } visited = set() order = [] def dfs(v) :     order.append(v)  # 방문 순서 기록, 출력값을 위해     for n in g[v] :         if n in visited :             continue         visited.add(n) # 방문 이력 기록, 방문했으면 더 방문하지 않도록         dfs(n) visited.add('A') dfs('A') print(order)

==== RESTART: C:/Users/yyhhm/OneDrive/바탕 화면/Main/사이버대학/4학기/데이터 구조와 활용/8-1.py === ['A', 'B', 'E', 'F', 'C', 'D', 'G']

- 재귀 방식의 원리 설명 : dfs('A')를 호출하면 시스템 호출 스택(Call Stack)에 쌓이며, 가장 깊이 들어간 정점부터 다시 호출이 종료되며 되돌아옴, 스택의 원리와 일치하나, 스택 구현 불필요

import collections g = {     'A' : ['B','C','D'],     'B' : ['A','E'],     'C' : ['A','F'],     'D' : ['A','G'],     'E' : ['B','F'],     'F' : ['C','E'],     'G' : ['D']     } visited = set() order = [] stack = collections.deque() visited.add('A') stack.append('A') while stack :     v = stack.pop()     order.append(v)          for n in reversed(g[v]) :         if n in visited :             continue         visited.add(n)         stack.append(n) print(order)

==== RESTART: C:/Users/yyhhm/OneDrive/바탕 화면/Main/사이버대학/4학기/데이터 구조와 활용/8-1.py === ['A', 'B', 'E', 'F', 'C', 'D', 'G']

- 스택 방식 원리 설명 : 명시적인 스택을 사용하면 DFS가 실제로 어떻게 동작하는지 보다 직관적으로 확인 가능, 최근에 추가한 점점(스택의 맨위)부터 깊이 탐색하여 깊이 우선 탐색이 명확히 드러남

- 두 방법의 비교

방법	장점	단점
재귀 방식	코드 간결하고 직관적	깊이가 매우 깊을 경우 호출 스택이 넘칠 수 있음
스택 방식	내부 동작을 명확히 이해 가능	코드가 복잡함

3. 깊이 우선 탐색 (DFS) 활용

(1) BOJ1260

import sys input = sys.stdin.readline def f(x):     res.append(x)     for y in a[x] :         if chk[y] == True :             continue         else :             chk[y] = True             f(y) n, m, v = map(int, input().split()) a = [[] for i in range(n+1)] for _ in range(m) :     x, y = map(int, input().split())     a[x].append(y)     a[y].append(x) for i in range(1, n+1) :     a[i].sort() chk = [False] * (n+1) chk[v] = True res = [] f(v) print(*res)

(2) BOJ11724

import sys input = sys.stdin.readline sys.setrecursionlimit(100000) def f(x):     res.append(x)     for y in a[x] :         if chk[y] == True :             continue         else :             chk[y] = True             f(y) n, m = map(int, input().split()) a = [[] for i in range(n+1)] for _ in range(m) :     x, y = map(int, input().split())     a[x].append(y)     a[y].append(x) for i in range(1, n+1) :     a[i].sort() chk = [False] * (n+1) chk[0] = True res = [] count = 0 for i in range(1, n+1) :     if chk[i] == True :         continue     else :         f(i)         count += 1 print(count)

(3) BOJ2606

import sys input = sys.stdin.readline sys.setrecursionlimit(100000) def f(x):     res.append(x)     for y in a[x] :         if chk[y] == True :             continue         else :             chk[y] = True             f(y)              n = int(input()) m = int(input()) a = [[] for i in range(n+1)] for _ in range(m) :     x, y = map(int, input().split())     a[x].append(y)     a[y].append(x) for i in range(1, n+1) :     a[i].sort() chk = [False] * (n+1) chk[1] = True res = [] f(1) print(len(res))