2. DFS(깊이 우선 탐색): 재귀 함수를 활용한 그래프 탐색 알고리즘의 이해

이미지 출처 - https://skilled.dev/course/depth-first-search

"그래프를 탐색하는 것은 미로를 탐험하는 것과 같습니다. DFS는 한 길을 끝까지 탐색한 후 다시 돌아와 다른 길을 탐색하는 방식으로, 깊이 있는 탐험을 선호하는 여행자와 같습니다."

목차

• 그래프 탐색의 기본 개념
• DFS란 무엇인가?
• DFS와 BFS의 차이점
• 재귀 함수의 이해
• DFS의 동작 원리
• 시간 복잡도 분석
• DFS 구현에 필요한 자료구조
• 실전 문제 분석: 백준 2667번
• 코드 구현 가이드
• 복습 전략 및 추천 문제
• 결론

---

그래프 탐색의 기본 개념

그래프 탐색이란 그래프 구조에서 모든 노드(정점)를 체계적으로 방문하는 과정입니다. 컴퓨터 과학에서 가장 기본적이면서도 중요한 알고리즘 중 하나로, 다양한 실생활 문제 해결에 응용됩니다.

그래프 탐색 알고리즘은 크게 너비 우선 탐색(BFS, Breadth-First Search)과 깊이 우선 탐색(DFS, Depth-First Search)으로 나뉩니다. 이 두 알고리즘은 그래프의 모든 노드를 방문한다는 공통점이 있지만, 노드를 방문하는 순서에 차이가 있습니다.

---

DFS란 무엇인가?

DFS(깊이 우선 탐색)는 그래프에서 가능한 한 깊이 들어가면서 탐색하는 알고리즘입니다. 한 경로를 끝까지 탐색한 후, 더 이상 탐색할 수 없다면 이전 위치로 돌아와 다른 경로를 탐색합니다.

마치 미로를 탐험할 때 한 길을 끝까지 가보고, 막다른 길에 도달하면 다시 뒤로 돌아와 다른 갈림길을 선택하는 것과 유사합니다.

DFS는 주로 다음과 같은 상황에서 활용됩니다:

• 경로 찾기 문제 (모든 가능한 경로 탐색)
• 사이클 탐지
• 위상 정렬
• 연결 요소 찾기
• 게임의 상태 공간 탐색 (예: 체스)

---

DFS와 BFS의 차이점

DFS와 BFS는 그래프 탐색의 두 가지 주요 방법으로, 서로 다른 특징을 가지고 있습니다:

특성	DFS (깊이 우선 탐색)	BFS (너비 우선 탐색)
탐색 방식	한 경로를 끝까지 탐색	레벨 단위로 탐색
자료구조	스택(Stack) 또는 재귀	큐(Queue)
구현 방법	재귀 함수 또는 스택	큐
최단 경로	최단 경로 보장하지 않음	최단 경로 보장 (가중치 없는 그래프)
메모리 사용	일반적으로 더 적게 사용	일반적으로 더 많이 사용
무한 그래프	무한 그래프에서도 사용 가능	무한 그래프에서 문제 발생 가능

탐색 순서 비교

다음과 같은 그래프가 있을 때:

    1
   / \
  2   5
 / \
3   4
     \
      6

• DFS 탐색 순서: 1 → 2 → 3 → 4 → 6 → 5
  • 가능한 깊이 들어가 탐색: 한 경로를 끝까지 탐색한 후 다른 경로 탐색
• BFS 탐색 순서: 1 → 2, 5 → 3, 4 → 6
  • 레벨 별로 탐색: 시작 노드(Level 0) → 인접 노드(Level 1) → 인접 노드의 인접 노드(Level 2)...

---

재귀 함수의 이해

DFS를 구현하는 가장 직관적인 방법은 재귀 함수(Recursive Function)를 사용하는 것입니다. 재귀 함수는 자기 자신을 호출하는 함수로, 복잡한 문제를 동일한 형태의 더 작은 문제로 나누어 해결하는 방식입니다.

재귀 함수의 핵심 요소

1. 기본 사례(Base Case): 재귀 호출을 멈추는 조건으로, 이 조건이 없으면 무한 호출이 발생합니다.
2. 재귀적 호출(Recursive Call): 함수가 자기 자신을 호출하는 부분입니다.
3. 상태 변화: 각 호출마다 문제의 상태가 기본 사례에 가까워지도록 변화해야 합니다.

재귀 함수 사용 시 주의사항

1. 스택 오버플로(Stack Overflow): 재귀 호출이 너무 깊어지면 스택 메모리가 초과될 수 있습니다.
2. 종료 조건: 반드시 재귀 호출을 종료하는 조건이 명확해야 합니다.
3. 중복 계산: 동일한 부분 문제가 반복해서 계산되는 것을 방지하기 위해 메모이제이션(Memoization) 기법을 사용할 수 있습니다.

재귀 함수는 마치 스택을 사용하는 것과 같은 방식으로 동작합니다. 함수 호출이 스택에 쌓이고, 가장 최근에 호출된 함수부터 실행이 완료되면서 스택에서 제거됩니다.

---

DFS의 동작 원리

DFS의 동작 원리를 단계별로 살펴보겠습니다:

1. 시작 노드를 방문 처리합니다.
2. 시작 노드의 인접 노드 중 아직 방문하지 않은 노드가 있다면, 그 노드로 이동하여 재귀적으로 DFS를 수행합니다.
3. 더 이상 방문할 인접 노드가 없다면, 이전 노드로 돌아갑니다(백트래킹).
4. 모든 노드를 방문할 때까지 2-3 과정을 반복합니다.

DFS 동작 예시 시각화

앞서 본 그래프에서 DFS 동작을 단계별로 살펴보겠습니다:

1. 노드 1 방문: 방문 = {1}
   • 인접 노드 2, 5 중 2 선택
2. 노드 2 방문: 방문 = {1, 2}
   • 인접 노드 3, 4 중 3 선택
3. 노드 3 방문: 방문 = {1, 2, 3}
   • 더 이상 방문할 인접 노드 없음, 노드 2로 돌아감
4. 노드 2에서 다음 인접 노드 4 방문: 방문 = {1, 2, 3, 4}
   • 인접 노드 6 선택
5. 노드 6 방문: 방문 = {1, 2, 3, 4, 6}
   • 더 이상 방문할 인접 노드 없음, 노드 4를 거쳐 노드 2로 돌아감
6. 노드 2에서 더 이상 방문할 인접 노드 없음, 노드 1로 돌아감
7. 노드 1에서 다음 인접 노드 5 방문: 방문 = {1, 2, 3, 4, 6, 5}
   • 더 이상 방문할 인접 노드 없음, DFS 종료

이런 식으로 재귀적인 호출 구조를 통해 그래프의 모든 노드를 깊이 우선으로 탐색합니다.

---

시간 복잡도 분석

DFS의 시간 복잡도는 그래프의 표현 방식과 크기에 따라 다릅니다:

• 인접 리스트 사용 시: O(V + E)
  • V: 정점(Vertex)의 개수
  • E: 간선(Edge)의 개수
  • 각 정점을 한 번씩 방문하고, 각 간선도 한 번씩 확인하므로 O(V + E)
• 인접 행렬 사용 시: O(V²)
  • 각 정점마다 인접한 모든 정점을 확인해야 하므로 O(V²)

일반적인 그래프 탐색 문제에서는 인접 리스트 표현이 더 효율적입니다. 이는 BFS의 시간 복잡도와 동일하지만, DFS는 재귀 호출을 사용하기 때문에 함수 호출 오버헤드가 존재할 수 있습니다.

---

DFS 구현에 필요한 자료구조

DFS를 효율적으로 구현하기 위해 다음과 같은 자료구조가 필요합니다:

1. 그래프 표현 (2가지 방법)

인접 행렬 (Adjacency Matrix)

# n개의 노드가 있는 그래프 표현
graph = [[0] * (n + 1) for _ in range(n + 1)]

# 노드 1과 2가 연결되어 있다면
graph[1][2] = 1
graph[2][1] = 1  # 양방향 그래프의 경우

인접 리스트 (Adjacency List)

# n개의 노드가 있는 그래프 표현
graph = [[] for _ in range(n + 1)]

# 노드 1과 2가 연결되어 있다면
graph[1].append(2)
graph[2].append(1)  # 양방향 그래프의 경우

2. 방문 여부 체크 배열

# 1차원 그래프의 경우
visited = [False] * (n + 1)

# 2차원 그래프(격자)의 경우
visited = [[False] * m for _ in range(n)]

3. 방향 벡터 (2차원 그래프에서 이동 시)

# 상, 우, 하, 좌 이동을 위한 방향 벡터
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

BFS와 달리 DFS는 재귀 함수를 사용하여 구현하므로 별도의 큐가 필요하지 않습니다. 시스템 스택이 암묵적으로 사용됩니다.

---

실전 문제 분석: 백준 2667번

백준 2667번 - 단지번호붙이기는 DFS를 활용하여 해결할 수 있는 대표적인 문제입니다.

문제 요약

• 2차원 배열의 지도가 주어집니다 (1은 집, 0은 빈 공간).
• 상하좌우로 연결된 집들의 모임을 단지라고 합니다.
• 각 단지에 번호를 붙이고, 단지 수와 각 단지내 집의 수를 오름차순으로 출력해야 합니다.

문제 해결 아이디어

1. 2차원 배열을 모두 탐색하며, 아직 방문하지 않은 집(1)을 찾습니다.
2. 집을 발견하면 DFS를 시작하여 연결된 모든 집을 방문 처리하고, 크기를 계산합니다.
3. 각 DFS 실행마다 발견한 단지의 크기를 리스트에 저장합니다.
4. 최종적으로 단지의 수와 각 단지의 크기를 오름차순으로 정렬하여 출력합니다.

시각화 예시

예를 들어, 다음과 같은 지도가 있다고 가정합시다:

1 1 0 1 1
0 1 0 0 0
0 0 0 0 0
1 0 1 1 1
1 0 1 1 1

여기서는 세 개의 단지가 있으며, 각각의 크기는 다음과 같습니다:

1. 좌상단 단지 (3개 집)
2. 우상단 단지 (2개 집)
3. 하단 단지 (6개 집)

DFS를 통해 각 단지를 탐색하고 크기를 계산하여 결과적으로 3, 2, 3, 6을 출력합니다.

---

코드 구현 가이드

백준 2667번 문제의 DFS 기반 해결책을 단계별로 구현해보겠습니다.

1. 입력 및 초기화

import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().strip())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

# 상, 우, 하, 좌 방향 벡터
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

result = []  # 각 단지의 크기를 저장할 리스트

2. DFS 함수 구현

def dfs(y, x):
    global each
    each += 1  # 단지 크기 증가

    for k in range(4):
        ny, nx = y + dy[k], x + dx[k]

        # 범위 체크
        if 0 <= ny < n and 0 <= nx < n:
            # 집이 있고 아직 방문하지 않았다면
            if graph[ny][nx] == 1 and not visited[ny][nx]:
                visited[ny][nx] = True
                dfs(ny, nx)  # 재귀적으로 DFS 호출

3. 전체 그래프 탐색

each = 0  # 각 단지의 크기를 저장할 변수

for y in range(n):
    for x in range(n):
        if graph[y][x] == 1 and not visited[y][x]:
            visited[y][x] = True
            each = 0  # 단지 크기 초기화
            dfs(y, x)  # DFS 수행
            result.append(each)  # 단지 크기 저장

# 결과 출력
result.sort()  # 오름차순 정렬
print(len(result))  # 단지 수 출력
for r in result:
    print(r)  # 각 단지의 크기 출력

전체 코드

import sys
input = sys.stdin.readline

n = int(input())
graph = [list(map(int, input().strip())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

result = []
each = 0

def dfs(y, x):
    global each
    each += 1  # 단지 크기 증가

    for k in range(4):
        ny, nx = y + dy[k], x + dx[k]

        if 0 <= ny < n and 0 <= nx < n:
            if graph[ny][nx] == 1 and not visited[ny][nx]:
                visited[ny][nx] = True
                dfs(ny, nx)

for y in range(n):
    for x in range(n):
        if graph[y][x] == 1 and not visited[y][x]:
            visited[y][x] = True
            each = 0  # 각 단지 크기 초기화
            dfs(y, x)
            result.append(each)

result.sort()
print(len(result))
for r in result:
    print(r)

---

복습 전략 및 추천 문제

DFS 알고리즘을 숙달하기 위한 효과적인 학습 전략을 소개합니다.

효과적인 학습 방법

1. 기본 구현 암기: DFS의 기본 템플릿을 외워두면 문제 해결 시간을 단축할 수 있습니다.
2. 다양한 문제 풀이: 서로 다른 유형의 DFS 문제를 풀어보며 응용력을 키우세요.
3. 코드 리뷰: 다른 사람의 코드를 분석하고 자신의 코드와 비교해보세요.
4. 시각화 도구 활용: 알고리즘 시각화 도구를 통해 DFS의 동작 과정을 이해하세요.

DFS 관련 추천 문제

1. 백준 1012 - 유기농 배추
   • 연결 요소 찾기 문제로, DFS의 기본 응용
2. 백준 2606 - 바이러스
   • 연결된 노드 수 세기 문제
3. 백준 11724 - 연결 요소의 개수
   • 그래프 내 연결 요소의 개수를 세는 문제
4. 백준 1987 - 알파벳
   • 백트래킹이 필요한 DFS 문제
5. 백준 10026 - 적록색약
   • 조건에 따라 다른 결과를 구하는 DFS 문제

이러한 문제들을 풀어보면서 DFS의 다양한 활용 방법을 익히고 재귀 함수의 동작 원리를 깊이 이해할 수 있습니다.

---

결론

DFS(깊이 우선 탐색)는 그래프 탐색의 기본 알고리즘으로, 재귀 함수를 통해 직관적으로 구현할 수 있습니다. 가능한 한 깊이 탐색하는 특성 때문에 모든 경로를 탐색하거나 특정 조건을 만족하는 경로를 찾는 데 유용합니다.

DFS의 핵심 요소 정리

1. 기본 원리: 현재 정점에서 갈 수 있는 정점까지 깊이 탐색한 후, 더 이상 갈 곳이 없다면 돌아오는 방식
2. 핵심 자료구조: 스택(Stack) 또는 재귀 함수(Recursion)
3. 시간 복잡도: O(V + E) (인접 리스트 사용 시)
4. 주요 응용 분야: 경로 탐색, 사이클 탐지, 위상 정렬, 연결 요소 찾기

실무에서의 활용

DFS는 알고리즘 문제 해결뿐만 아니라 다양한 분야에서 활용됩니다:

• 게임 AI: 최선의 수를 탐색하는 알고리즘의 기초
• 웹 크롤링: 웹사이트의 모든 링크를 탐색하는 과정
• 네트워크 분석: 네트워크의 연결성 파악
• 컴파일러: 구문 분석 트리 생성

재귀 함수에 익숙해지고 DFS의 기본 원리를 이해한다면, 그래프 관련 문제를 효과적으로 해결할 수 있는 역량이 향상될 것입니다. 무엇보다 종료 조건을 명확히 설정하고 스택 오버플로에 주의하면서 코드를 작성하는 습관을 들이는 것이 중요합니다.

---

참고 자료

• Introduction to Algorithms (CLRS)
• 백준 온라인 저지 - 그래프 탐색 문제 모음
• 알고리즘 시각화 도구 - VisuAlgo
• 파이썬 알고리즘 인터뷰 - 박상길 저
• 프로그래머스 코딩테스트 연습 - BFS/DFS