깊이 우선 탐색

DFS : Depth-First Search
DFS는 그래프나 트리 구조에서 한 방향으로 계속 파고 들어가다가,
더 이상 갈 곳이 없으면 다시 뒤로 돌아와서 다른 경로로 가보는 탐색 방식이다.

갈림길이 있더라도 일단 끝까지 쭈우우욱 들어가보고, 막혔다면 다시 돌아와서 안가본 길을 가본다.

자신의 길을 믿고 한 우물만 쭉 파보는 우직한 녀석이다.

기본적으로 DFS는 스택 자료구조의 형식이다.
파이썬에서는 재귀 함수를 활용해 DFS를 간단하게 구현할 수 있다.
하지만 숙달되었다면 스택 방식도 공부하는 것이 좋겠다.

DFS 재귀 구현 절차

1. 입력값을 정의하거나 입력을 받는다.

   • 정점 수, 간선 수, 시작 정점
   • 간선 정보

2. 그래프를 인접 리스트로 구성한다.

   • 간선을 양방향(또는 단방향)으로 추가
   • (선택) 방문 순서를 정해주고 싶다면 정렬

3. 방문 여부를 체크할 리스트를 만든다.

4. DFS 함수(재귀)를 정의한다.

   • 현재 노드 방문 처리
   • 연결된 노드 중 방문하지 않은 곳으로 재귀 호출

5. 시작 정점에서 DFS를 호출한다.

예제 코드

import sys
sys.setrecursionlimit(10**6)  # 재귀 깊이 한도 확장

# 1. 예시 입력: 정점 수 N, 간선 수 M, 시작 정점 start
N, M, start = 5, 4, 1
edges = [
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 5)
]

# 2. 그래프 초기화 (인접 리스트)
graph = [[] for _ in range(N + 1)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # 무방향 그래프일 경우 양방향 연결

# 3. 이웃 노드 방문 순서 정렬 (선택 사항)
for node in range(1, N + 1):
    graph[node].sort()

# 4. 방문 여부 리스트 생성
visited = [False] * (N + 1)

# 5. DFS 함수 정의 (재귀 방식)
def dfs(node):
    visited[node] = True
    print(f"{node} 방문")  # 방문 시 할 작업

    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor)

# 6. DFS 시작
dfs(start)

---

sys.setrecursionlimit()이란?

파이썬은 기본적으로 재귀 함수 호출 깊이에 제한(약 1000단계)이 걸려 있다.
하지만 DFS처럼 수천 개의 노드를 재귀로 탐색하려면 이 제한을 초과할 수 있다.

그래서 아래 코드처럼 제한을 늘려줘야 한다.

import sys
sys.setrecursionlimit(10**6)

너무 큰 값으로 설정하면 메모리 부족이나 런타임 에러가 날 수 있으니 적절히 사용해야 한다.

---

정리

• DFS는 재귀를 사용해 간결하고 직관적인 코드로 구현 가능
• visited 리스트는 무한 루프 방지를 위해 필수
• 정점 방문 순서를 제어하고 싶다면 graph[node].sort()를 활용
• 재귀 깊이 제한을 피하려면 sys.setrecursionlimit() 설정 필요

---

너비 우선 탐색(BFS) - 큐 기반 구현 방법

BFS(Breadth-First Search, 너비 우선 탐색)는
가까운 노드부터 차례대로 탐색하는 그래프 탐색 알고리즘이다.

DFS가 한 방향으로 깊이 파고드는 방식이라면,
BFS는 넓게 퍼지듯이 탐색하는 방식이며,
그래프에서 최단 거리를 구할 때 매우 자주 사용된다.

파이썬에서는 collections.deque를 사용하여 큐(Queue) 자료구조를 구현한다.

---

BFS 구현 절차 + 예제 코드

from collections import deque

# 1. 입력값 정의: 정점 수, 간선 수, 시작 정점
N, M, start = 5, 4, 1
edges = [
    (1, 2),
    (1, 3),
    (2, 4),
    (3, 5)
]

# 2. 그래프 초기화 (인접 리스트)
graph = [[] for _ in range(N + 1)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # 무방향 그래프일 경우 양쪽 연결

# 3. 이웃 노드 방문 순서 정렬 (선택 사항)
for node in range(1, N + 1):
    graph[node].sort()

# 4. 방문 여부 리스트 생성
visited = [False] * (N + 1)

# 5. BFS 함수 정의 (큐 기반)
def bfs(start):
    queue = deque([start])
    visited[start] = True

    while queue:
        node = queue.popleft()
        print(f"{node} 방문")  # 방문 시 처리할 작업

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

# 6. BFS 시작
bfs(start)

---

핵심 요약

• BFS는 가까운 노드부터 차례로 탐색하는 알고리즘이다.
• deque를 사용해 효율적인 큐를 구현할 수 있다.
• visited 리스트를 통해 중복 방문을 방지한다.
• 탐색 순서를 제어하고 싶다면 graph[node].sort()를 사용할 수 있다.

---