DFS와 BFS — 그래프 탐색 알고리즘의 선택 기준·구현·코딩테스트 실전 가이드

# 인접 행렬 — 노드 수 적고 간선 많을 때 유리
graph = [
    [0, 1, 1, 0, 0],  # 노드 0
    [1, 0, 0, 1, 0],  # 노드 1
    [1, 0, 0, 1, 1],  # 노드 2
    [0, 1, 1, 0, 1],  # 노드 3
    [0, 0, 1, 1, 0],  # 노드 4
]

# 인접 리스트 — 코딩테스트에서 가장 많이 사용
graph = [
    [1, 2],     # 노드 0과 연결: 1, 2
    [0, 3],     # 노드 1과 연결: 0, 3
    [0, 3, 4],  # 노드 2와 연결: 0, 3, 4
    [1, 2, 4],  # 노드 3과 연결: 1, 2, 4
    [2, 3],     # 노드 4와 연결: 2, 3
]

1. 시작 노드를 스택에 넣고 방문 표시
2. 스택 최상단 노드의 미방문 인접 노드가 있으면
   → 그 노드를 스택에 넣고 방문 표시
3. 미방문 인접 노드가 없으면
   → 스택에서 현재 노드를 꺼냄 (백트래킹)
4. 스택이 빌 때까지 2~3 반복

# Python — DFS 재귀 구현
def dfs(graph, v, visited):
    visited[v] = True           # 현재 노드 방문 표시
    print(v, end=' ')           # 방문 순서 출력

    for neighbor in graph[v]:   # 인접 노드 순회
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

# 사용 예시
graph = [
    [],           # 0번 노드 (인덱스 맞추기)
    [2, 3, 8],    # 1번 노드와 연결: 2, 3, 8
    [1, 7],       # 2번 노드와 연결: 1, 7
    [1, 4, 5],    # 3번 노드와 연결: 1, 4, 5
    [3, 5],       # 4번 노드와 연결: 3, 5
    [3, 4],       # 5번 노드와 연결: 3, 4
    [7],          # 6번 노드와 연결: 7
    [2, 6, 8],    # 7번 노드와 연결: 2, 6, 8
    [1, 7],       # 8번 노드와 연결: 1, 7
]
visited = [False] * 9
dfs(graph, 1, visited)
# 출력: 1 2 7 6 8 3 4 5

def dfs_stack(graph, start):
    visited = set()
    stack = [start]

    while stack:
        v = stack.pop()         # 스택에서 노드 꺼냄
        if v not in visited:
            visited.add(v)
            print(v, end=' ')
            # 인접 노드를 역순으로 넣어야 원래 순서로 탐색됨
            for neighbor in reversed(graph[v]):
                if neighbor not in visited:
                    stack.append(neighbor)

import java.util.*;

public class DFS {
    static int[] visited;
    static List<List<Integer>> graph;

    public static void dfs(int v) {
        visited[v] = 1;
        System.out.print(v + " ");

        for (int neighbor : graph.get(v)) {
            if (visited[neighbor] == 0) {
                dfs(neighbor);
            }
        }
    }

    public static void main(String[] args) {
        int n = 9; // 노드 수
        graph = new ArrayList<>();
        visited = new int[n];

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가
        graph.get(1).addAll(Arrays.asList(2, 3, 8));
        graph.get(2).addAll(Arrays.asList(1, 7));
        // ... 나머지 간선 추가

        dfs(1);
    }
}

1. 시작 노드를 큐에 넣고 방문 표시
2. 큐에서 노드를 꺼내 해당 노드의 미방문 인접 노드를
   모두 큐에 넣고 방문 표시
3. 큐가 빌 때까지 2 반복

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])      # 시작 노드를 큐에 삽입
    visited[start] = True       # 방문 처리

    while queue:
        v = queue.popleft()     # 큐에서 원소 꺼냄 (선입선출)
        print(v, end=' ')

        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)      # 큐에 삽입
                visited[neighbor] = True    # 방문 표시

# 사용 예시 (위와 동일한 그래프)
visited = [False] * 9
bfs(graph, 1, visited)
# 출력: 1 2 3 8 7 4 5 6

from collections import deque

def bfs_shortest(graph, start, end):
    queue = deque([(start, 0)])  # (현재 노드, 현재까지 거리)
    visited = {start}

    while queue:
        v, dist = queue.popleft()

        if v == end:
            return dist          # 목적지 도달 시 최단 거리 반환

        for neighbor in graph[v]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1  # 경로 없음

import java.util.*;

public class BFS {
    public static void bfs(List<List<Integer>> graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");

            for (int neighbor : graph.get(v)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }
}

        1
       / \
      2   3
     / \   \
    4   5   6

# N개 중 M개를 고르는 조합 — DFS 백트래킹
def dfs_combination(start, path, n, m, result):
    if len(path) == m:
        result.append(path[:])
        return
    for i in range(start, n + 1):
        path.append(i)
        dfs_combination(i + 1, path, n, m, result)
        path.pop()  # 백트래킹 — 선택 취소

# 미로 탈출 최단 경로 — BFS 전형 문제
from collections import deque

def maze_shortest(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    queue = deque([(start[0], start[1], 0)])  # (행, 열, 거리)
    visited = [[False] * cols for _ in range(rows)]
    visited[start[0]][start[1]] = True

    dx = [-1, 1, 0, 0]  # 상하좌우
    dy = [0, 0, -1, 1]

    while queue:
        x, y, dist = queue.popleft()

        if (x, y) == end:
            return dist

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < rows and 0 <= ny < cols:
                if not visited[nx][ny] and maze[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append((nx, ny, dist + 1))
    return -1

# 멀티 소스 BFS — 여러 출발점에서 동시에 시작
def multi_source_bfs(grid, sources):
    queue = deque()
    for r, c in sources:
        queue.append((r, c, 0))
        grid[r][c] = 1  # 방문 표시
    # 이후 일반 BFS와 동일

"DFS와 BFS는 모두 그래프의 모든 노드를 탐색하는 알고리즘이지만
탐색 순서와 사용 자료구조가 다릅니다.

DFS(깊이 우선 탐색)는 스택 또는 재귀를 사용해
한 방향으로 끝까지 탐색한 뒤 돌아오는 방식입니다.
경우의 수 탐색, 백트래킹, 사이클 감지에 적합합니다.

BFS(너비 우선 탐색)는 큐를 사용해
출발점에서 가까운 노드부터 레벨 단위로 탐색하는 방식입니다.
가중치 없는 그래프의 최단 경로 보장이 가장 큰 장점입니다.

시간 복잡도는 둘 다 O(V + E)로 동일하며,
최단 경로가 필요하면 BFS, 모든 경우를 탐색해야 하면 DFS를 선택합니다."

# 방법 1: 재귀 깊이 제한 늘리기
import sys
sys.setrecursionlimit(100000)

# 방법 2: 재귀 대신 명시적 스택으로 구현
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.add(v)
            for neighbor in reversed(graph[v]):
                if neighbor not in visited:
                    stack.append(neighbor)

# 2D 격자 탐색 공통 패턴
dx = [-1, 1, 0, 0]   # 상, 하, 좌, 우 (행 방향)
dy = [0, 0, -1, 1]   # 상, 하, 좌, 우 (열 방향)

for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < rows and 0 <= ny < cols:  # 경계 확인
        # 탐색 조건 처리

# N-Queen 백트래킹 핵심 구조
def solve(row, n, queens, result):
    if row == n:                    # 모든 퀸 배치 완료
        result.append(queens[:])
        return
    for col in range(n):
        if is_safe(queens, row, col):
            queens.append(col)      # 선택
            solve(row + 1, n, queens, result)
            queens.pop()            # 백트래킹 — 선택 취소