안동민 개발노트

BFS와 DFS는 둘 다 그래프를 방문하지만 목적이 다릅니다. 무가중치 최단 거리는 BFS가 기본이고, 경로를 깊게 따라 구조를 확인할 때는 DFS가 편합니다. 그래서 코드를 외우기 전에 이 문제에서 무엇을 구하는지를 우선 정해야 합니다.

자주 틀리는 지점은 방문 체크 시점입니다. enqueue/push 전에 방문 처리를 하지 않으면 같은 노드가 중복으로 쌓일 수 있습니다. 여기서는 템플릿 암기보다 선택 관점과 상태 관리 규칙을 함께 익히는 데 집중합니다.

BFS와 DFS 선택 및 방문 체크 흐름 요약

핵심 원리 프레임

탐색 문제는 코드를 쓰기 전에 무엇을 구하는지를 우선 고르면 훨씬 단순해집니다. 지금 문제가 거리 계산인지 구조 확인인지 우선 표시하고 시작하세요.

BFS는 가까운 정점부터 레벨 단위로 넓게 방문하는 탐색입니다. 큐를 사용해 같은 거리의 정점을 우선 처리하기 때문에 무가중치 최단 거리에 기본 선택이 됩니다. 시작점에서 1번 간선 거리 정점을 모두 처리한 다음 2번 거리 정점으로 넘어가는 흐름이 핵심입니다.

DFS는 한 경로를 끝까지 내려갔다가 되돌아오는 탐색입니다. 스택이나 재귀를 사용해 깊이 우선으로 확장하며 경로 구조 분석, 사이클 검사 같은 문제에 자주 쓰입니다. 1->2->4를 끝까지 본 뒤 되돌아와 1->3으로 가는 흐름이 대표적인 동작입니다.

방문 체크 시점은 중복 삽입과 메모리 사용량을 좌우하는 상태 관리 규칙입니다. 노드를 넣을 때 방문 처리할지, 꺼낼 때 처리할지 정책을 처음에 고정해야 구현이 흔들리지 않습니다. BFS에서는 enqueue 시점 방문 처리가 일반적으로 안전하며 같은 노드가 큐에 여러 번 들어가는 문제를 막습니다.

BFS/DFS 선택이 운영에 미치는 영향

탐색 선택이 틀리면 정답이 틀릴 뿐 아니라 성능도 나빠집니다.
예를 들어 무가중치 최단 거리 문제를 DFS로 억지 구현하면 추가 상태 관리가 복잡해집니다.

또한 방문 체크 시점이 늦으면 큐/스택에 중복 노드가 쌓여 메모리 사용량이 급증합니다.

방문 처리 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

간단한 그래프에서 BFS와 DFS 방문 순서를 비교합니다.

그래프: 1->[2,3], 2->[4], 3->[5]
시작 정점: 1

BFS는 큐를 사용해 레벨 순서 1,2,3,4,5로 방문합니다.
DFS는 스택/재귀로 경로를 깊게 따라가 1,2,4,3,5가 될 수 있습니다.
무가중치 최단 거리에는 BFS가 기본 선택입니다.

그래프 탐색: BFS 기본 템플릿

문제 의도: 큐 기반 BFS의 기본 골격과 방문 체크 시점을 익힙니다.
입력 예시: graph={1:[2,3],2:[4],3:[4,5],4:[],5:[]}, start=1
출력 예시: 방문 순서 [1,2,3,4,5]

main.cpp

#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

vector<int> bfs(const unordered_map<int, vector<int>>& graph, int start) {
    unordered_set<int> visited = {start};
    queue<int> q;
    q.push(start);
    vector<int> order;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        order.push_back(cur);
        auto it = graph.find(cur);
        if (it == graph.end()) continue;
        for (int nxt : it->second) {
            if (visited.count(nxt)) continue;
            visited.insert(nxt);
            q.push(nxt);
        }
    }
    return order;
}

int main() {
    unordered_map<int, vector<int>> g = {{1, {2, 3}}, {2, {4}}, {3, {4, 5}}, {4, {}}, {5, {}}};
    auto order = bfs(g, 1);
    for (int x : order) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new ArrayDeque<>();
        List<Integer> order = new ArrayList<>();

        visited.add(start);
        q.offer(start);

        while (!q.isEmpty()) {
            int cur = q.poll();
            order.add(cur);
            for (int nxt : graph.getOrDefault(cur, List.of())) {
                if (visited.contains(nxt)) continue;
                visited.add(nxt);
                q.offer(nxt);
            }
        }
        return order;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> g = Map.of(
            1, List.of(2, 3),
            2, List.of(4),
            3, List.of(4, 5),
            4, List.of(),
            5, List.of()
        );
        System.out.println(bfs(g, 1));
    }
}

main.py

from collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    order = []

    while q:
        cur = q.popleft()
        order.append(cur)

        for nxt in graph.get(cur, []):
            if nxt in visited:
                continue
            visited.add(nxt)
            q.append(nxt)

    return order

g = {1: [2, 3], 2: [4], 3: [4, 5], 4: [], 5: []}
print(bfs(g, 1))  # [1, 2, 3, 4, 5]

main.rs

use std::collections::{HashMap, HashSet, VecDeque};

fn bfs(graph: &HashMap<i32, Vec<i32>>, start: i32) -> Vec<i32> {
    let mut visited = HashSet::new();
    let mut q = VecDeque::new();
    let mut order = Vec::new();

    visited.insert(start);
    q.push_back(start);

    while let Some(cur) = q.pop_front() {
        order.push(cur);
        if let Some(neis) = graph.get(&cur) {
            for &nxt in neis {
                if visited.contains(&nxt) {
                    continue;
                }
                visited.insert(nxt);
                q.push_back(nxt);
            }
        }
    }
    order
}

fn main() {
    let mut g = HashMap::new();
    g.insert(1, vec![2, 3]);
    g.insert(2, vec![4]);
    g.insert(3, vec![4, 5]);
    g.insert(4, vec![]);
    g.insert(5, vec![]);
    println!("{:?}", bfs(&g, 1));
}

BFS/DFS 결과 그래프 모델 조건 검토

BFS는 큐에 들어간 순서가 곧 탐색 레벨을 의미합니다.
방문 체크를 enqueue 시점에 해야 중복 삽입이 줄어듭니다.
레벨 기반 정보(최단 거리, 층별 처리)를 얻기 쉬운 이유가 여기에 있습니다.

평균 시간복잡도: O(V + E)
최악 시간복잡도: O(V + E)
공간복잡도: O(V)

그래프 탐색: 반복 DFS 템플릿

문제 의도: 재귀 없이 스택으로 DFS를 구현해 상태 관리를 명시적으로 다룹니다.
입력 예시: graph={1:[2,3],2:[4],3:[4,5],4:[],5:[]}, start=1
출력 예시: 방문 순서 예시 [1,2,4,3,5]

main.cpp

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

vector<int> dfsIterative(const unordered_map<int, vector<int>>& graph, int start) {
    unordered_set<int> visited;
    vector<int> stack = {start};
    vector<int> order;

    while (!stack.empty()) {
        int cur = stack.back();
        stack.pop_back();
        if (visited.count(cur)) continue;
        visited.insert(cur);
        order.push_back(cur);

        auto it = graph.find(cur);
        if (it == graph.end()) continue;
        const auto& nxts = it->second;
        for (int i = (int)nxts.size() - 1; i >= 0; --i) {
            int nxt = nxts[i];
            if (!visited.count(nxt)) stack.push_back(nxt);
        }
    }
    return order;
}

int main() {
    unordered_map<int, vector<int>> g = {{1, {2, 3}}, {2, {4}}, {3, {4, 5}}, {4, {}}, {5, {}}};
    auto order = dfsIterative(g, 1);
    for (int x : order) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static List<Integer> dfsIterative(Map<Integer, List<Integer>> graph, int start) {
        Set<Integer> visited = new HashSet<>();
        List<Integer> stack = new ArrayList<>();
        List<Integer> order = new ArrayList<>();
        stack.add(start);

        while (!stack.isEmpty()) {
            int cur = stack.remove(stack.size() - 1);
            if (visited.contains(cur)) continue;
            visited.add(cur);
            order.add(cur);

            List<Integer> nxts = graph.getOrDefault(cur, List.of());
            for (int i = nxts.size() - 1; i >= 0; i--) {
                int nxt = nxts.get(i);
                if (!visited.contains(nxt)) stack.add(nxt);
            }
        }
        return order;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> g = Map.of(
            1, List.of(2, 3),
            2, List.of(4),
            3, List.of(4, 5),
            4, List.of(),
            5, List.of()
        );
        System.out.println(dfsIterative(g, 1));
    }
}

main.py

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

    while stack:
        cur = stack.pop()
        if cur in visited:
            continue

        visited.add(cur)
        order.append(cur)

        for nxt in reversed(graph.get(cur, [])):
            if nxt not in visited:
                stack.append(nxt)

    return order

g = {1: [2, 3], 2: [4], 3: [4, 5], 4: [], 5: []}
print(dfs_iterative(g, 1))  # [1, 2, 4, 3, 5]

main.rs

use std::collections::{HashMap, HashSet};

fn dfs_iterative(graph: &HashMap<i32, Vec<i32>>, start: i32) -> Vec<i32> {
    let mut visited = HashSet::new();
    let mut stack = vec![start];
    let mut order = Vec::new();

    while let Some(cur) = stack.pop() {
        if visited.contains(&cur) {
            continue;
        }
        visited.insert(cur);
        order.push(cur);

        if let Some(nxts) = graph.get(&cur) {
            let mut idx = nxts.len();
            while idx > 0 {
                idx -= 1;
                let nxt = nxts[idx];
                if !visited.contains(&nxt) {
                    stack.push(nxt);
                }
            }
        }
    }
    order
}

fn main() {
    let mut g = HashMap::new();
    g.insert(1, vec![2, 3]);
    g.insert(2, vec![4]);
    g.insert(3, vec![4, 5]);
    g.insert(4, vec![]);
    g.insert(5, vec![]);
    println!("{:?}", dfs_iterative(&g, 1));
}

BFS/DFS 결과 방문 순서 추적

반복 DFS는 재귀 스택을 명시적 스택으로 바꾼 구현입니다.
깊은 그래프에서도 재귀 제한에 덜 민감합니다.
reversed를 사용하면 탐색 순서를 예측 가능하게 유지할 수 있습니다.

평균 시간복잡도: O(V + E)
공간복잡도: O(V)

그래프 탐색: BFS 최단 거리

문제 의도: BFS로 시작 정점에서 각 정점까지 최소 간선 수를 계산합니다.
입력 예시: graph={1:[2,3],2:[4],3:[4,5],4:[],5:[]}, start=1
출력 예시: 거리 맵 {1:0,2:1,3:1,4:2,5:2}

main.cpp

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<int, int> shortestDist(const unordered_map<int, vector<int>>& graph, int start) {
    unordered_map<int, int> dist;
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        auto it = graph.find(cur);
        if (it == graph.end()) continue;
        for (int nxt : it->second) {
            if (dist.count(nxt)) continue;
            dist[nxt] = dist[cur] + 1;
            q.push(nxt);
        }
    }
    return dist;
}

int main() {
    unordered_map<int, vector<int>> g = {{1, {2, 3}}, {2, {4}}, {3, {4, 5}}, {4, {}}, {5, {}}};
    auto dist = shortestDist(g, 1);
    for (auto& [k, v] : dist) cout << k << ":" << v << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static Map<Integer, Integer> shortestDist(Map<Integer, List<Integer>> graph, int start) {
        Map<Integer, Integer> dist = new HashMap<>();
        Queue<Integer> q = new ArrayDeque<>();
        dist.put(start, 0);
        q.offer(start);

        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int nxt : graph.getOrDefault(cur, List.of())) {
                if (dist.containsKey(nxt)) continue;
                dist.put(nxt, dist.get(cur) + 1);
                q.offer(nxt);
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> g = Map.of(
            1, List.of(2, 3),
            2, List.of(4),
            3, List.of(4, 5),
            4, List.of(),
            5, List.of()
        );
        System.out.println(shortestDist(g, 1));
    }
}

main.py

from collections import deque

def shortest_dist(graph, start):
    dist = {start: 0}
    q = deque([start])

    while q:
        cur = q.popleft()
        for nxt in graph.get(cur, []):
            if nxt in dist:
                continue
            dist[nxt] = dist[cur] + 1
            q.append(nxt)

    return dist

g = {1: [2, 3], 2: [4], 3: [4, 5], 4: [], 5: []}
print(shortest_dist(g, 1))  # {1: 0, 2: 1, 3: 1, 4: 2, 5: 2}

main.rs

use std::collections::{HashMap, VecDeque};

fn shortest_dist(graph: &HashMap<i32, Vec<i32>>, start: i32) -> HashMap<i32, i32> {
    let mut dist = HashMap::new();
    let mut q = VecDeque::new();
    dist.insert(start, 0);
    q.push_back(start);

    while let Some(cur) = q.pop_front() {
        let cur_d;
        if let Some(value) = dist.get(&cur) {
            cur_d = *value;
        } else {
            continue;
        }
        if let Some(nxts) = graph.get(&cur) {
            for &nxt in nxts {
                if dist.contains_key(&nxt) {
                    continue;
                }
                dist.insert(nxt, cur_d + 1);
                q.push_back(nxt);
            }
        }
    }
    dist
}

fn main() {
    let mut g = HashMap::new();
    g.insert(1, vec![2, 3]);
    g.insert(2, vec![4]);
    g.insert(3, vec![4, 5]);
    g.insert(4, vec![]);
    g.insert(5, vec![]);
    println!("{:?}", shortest_dist(&g, 1));
}