안동민 개발노트

순서가 있는 그래프 문제는 보통 DAG(사이클 없는 방향 그래프)로 모델링합니다. DAG DP에서 가장 먼저 할 일은 점화식이 아니라 계산 순서(위상 정렬)를 확보하는 것입니다. 순서가 없으면 아직 계산되지 않은 값을 참조하게 되어 오답이 납니다.

여기서는 위상 정렬과 DP를 분리하지 않고 한 흐름으로 설명합니다.

위상 순서를 만들고, 2) 그 순서대로 전이합니다. 이 기본 순서만 지켜도 DAG 문제의 실수를 크게 줄일 수 있습니다.

핵심 패턴 프레임: DAG 위상 전개

DAG DP는 점화식보다 계산 순서를 우선 고정하면 구현이 안정됩니다. 코드를 쓰기 전에 전이를 어떤 순서로 진행할지 한 줄로 써 보세요.

위상 정렬은 선행 조건을 만족하도록 정점을 선형 순서로 나열하는 절차입니다. DAG에서 모든 간선 u->v가 있을 때 u가 v보다 앞에 오도록 만든 순서가 위상 순서입니다. 1->2, 1->3 구조라면 어떤 유효 순서에서도 정점 1은 반드시 2와 3보다 앞에 위치합니다.

DAG DP 전이는 위상 순서를 따라 값을 앞에서 뒤로 전달하는 계산입니다. 사이클이 없다는 전제를 이용해 dp[next]를 이미 계산된 dp[cur]로 안전하게 갱신할 수 있습니다. 최장 경로 문제에서는 dp[v]=max(dp[v], dp[u]+w)를 u->v 간선마다 위상 순서대로 적용합니다.

DAG 전제 조건은 그래프에 사이클이 없어야 한다는 요구입니다. 사이클이 있으면 위상 순서를 만들 수 없고, 아직 확정되지 않은 값이 다시 현재를 참조해 점화식이 깨집니다. Kahn 알고리즘에서 처리 정점 수가 전체보다 적게 끝나면 사이클이 있으므로 DP를 바로 중단해야 합니다.

DAG 처리 실전 장애와 연결하기

순서 없는 그래프에서는 미래 상태가 현재 상태에 다시 영향을 줄 수 있습니다.
이 경우 단순 DP 전이로는 정답을 보장하기 어렵습니다.

반면 DAG는 순환이 없어서 앞에서 뒤로 계산이 가능합니다.
이 구조 덕분에 최장 경로, 경로 수, 누적 비용 같은 문제를 효율적으로 풀 수 있습니다.

위상 정렬 테스트로 빠르게 검증하기

학습 효율을 높이려면 오답 -> 디버깅 -> 교정 -> 검증 순서로 로그를 남기면서 진행하는 것이 가장 빠릅니다.

DAG 전이 순서를 우선 만든 뒤 계산하는 과정을 따라가 봅니다.

간선: 1->2, 1->3, 2->4, 3->4
시작 정점: 1

Kahn으로 위상 순서를 구합니다(예: 1,2,3,4).
순서대로 정점을 처리하며 dp[next]를 갱신합니다.
사이클이 있으면 위상 순서가 완성되지 않으므로 DP를 중단해야 합니다.

DAG: Kahn 위상 정렬

문제 의도: DAG 전이의 기반이 되는 위상 순서를 계산합니다.
입력 예시: n=4, edges=[(1,2),(1,3),(2,4),(3,4)]
출력 예시: 위상 순서 [1,2,3,4] 또는 None

main.cpp

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

vector<int> topoOrder(int n, const vector<pair<int, int>>& edges) {
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        g[u].push_back(v);
        indeg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) if (indeg[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        order.push_back(cur);
        for (int nxt : g[cur]) {
            indeg[nxt]--;
            if (indeg[nxt] == 0) q.push(nxt);
        }
    }
    return (int)order.size() == n ? order : vector<int>{};
}

int main() {
    auto order = topoOrder(4, {{1, 2}, {1, 3}, {2, 4}, {3, 4}});
    for (int x : order) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static List<Integer> topoOrder(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        int[] indeg = new int[n + 1];
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            g.get(u).add(v);
            indeg[v]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.offer(i);
        List<Integer> order = new ArrayList<>();

        while (!q.isEmpty()) {
            int cur = q.poll();
            order.add(cur);
            for (int nxt : g.get(cur)) {
                indeg[nxt]--;
                if (indeg[nxt] == 0) q.offer(nxt);
            }
        }
        return order.size() == n ? order : null;
    }

    public static void main(String[] args) {
        System.out.println(topoOrder(4, new int[][]{{1,2},{1,3},{2,4},{3,4}}));
    }
}

main.py

from collections import defaultdict, deque

def topo_order(n, edges):
    g = defaultdict(list)
    indeg = [0] * (n + 1)

    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1

    q = deque([i for i in range(1, n + 1) if indeg[i] == 0])
    order = []

    while q:
        cur = q.popleft()
        order.append(cur)
        for nxt in g[cur]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)

    return order if len(order) == n else None

print(topo_order(4, [(1,2), (1,3), (2,4), (3,4)]))  # [1,2,3,4] 등

main.rs

use std::collections::VecDeque;

fn topo_order(n: usize, edges: &[(usize, usize)]) -> Option<Vec<usize>> {
    let mut g = vec![Vec::new(); n + 1];
    let mut indeg = vec![0usize; n + 1];
    for &(u, v) in edges {
        g[u].push(v);
        indeg[v] += 1;
    }

    let mut q = VecDeque::new();
    for i in 1..=n {
        if indeg[i] == 0 {
            q.push_back(i);
        }
    }

    let mut order = Vec::new();
    while let Some(cur) = q.pop_front() {
        order.push(cur);
        for &nxt in &g[cur] {
            indeg[nxt] -= 1;
            if indeg[nxt] == 0 {
                q.push_back(nxt);
            }
        }
    }

    if order.len() == n { Some(order) } else { None }
}

fn main() {
    println!("{:?}", topo_order(4, &[(1, 2), (1, 3), (2, 4), (3, 4)]));
}

위상 정렬/DAG DP 동작 초기 거리값 검토

진입 차수 0 노드를 제거해 나가며 순서를 만듭니다.
모든 노드를 방문하지 못하면 사이클이 존재하는 것입니다.
위상 정렬 성공 여부 자체가 DAG 판정으로 사용됩니다.

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

DAG: DAG 최장 경로

문제 의도: 위상 순서를 이용해 DAG에서 시작점 기준 최장 경로를 계산합니다.
입력 예시: 가중치 DAG 간선, start=1
출력 예시: 각 정점까지 최장 거리 배열

main.cpp

#include <algorithm>
#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;

vector<long long> longestPathDag(int n, const vector<tuple<int, int, int>>& edges, int start) {
    vector<vector<pair<int, int>>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (const auto& edge : edges) {
        int u = get<0>(edge);
        int v = get<1>(edge);
        int w = get<2>(edge);
        g[u].push_back({v, w});
        indeg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) if (indeg[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        order.push_back(cur);
        for (const auto& edge : g[cur]) {
            int nxt = edge.first;
            indeg[nxt]--;
            if (indeg[nxt] == 0) q.push(nxt);
        }
    }
    if ((int)order.size() != n) return {};

    const long long NEG_INF = -(1LL << 60);
    vector<long long> dp(n + 1, NEG_INF);
    dp[start] = 0;
    for (int cur : order) {
        if (dp[cur] == NEG_INF) continue;
        for (const auto& edge : g[cur]) {
            int nxt = edge.first;
            int w = edge.second;
            dp[nxt] = max(dp[nxt], dp[cur] + w);
        }
    }
    return dp;
}

int main() {
    vector<tuple<int, int, int>> edges = {{1,2,3}, {1,3,2}, {2,4,4}, {3,4,1}};
    auto dp = longestPathDag(4, edges, 1);
    for (int i = 1; i <= 4; ++i) cout << dp[i] << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static long[] longestPathDag(int n, int[][] edges, int start) {
        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        int[] indeg = new int[n + 1];
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            g.get(u).add(new int[]{v, w});
            indeg[v]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.offer(i);
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int cur = q.poll();
            order.add(cur);
            for (int[] nxt : g.get(cur)) {
                indeg[nxt[0]]--;
                if (indeg[nxt[0]] == 0) q.offer(nxt[0]);
            }
        }
        if (order.size() != n) return null;

        long NEG_INF = -(1L << 60);
        long[] dp = new long[n + 1];
        Arrays.fill(dp, NEG_INF);
        dp[start] = 0;
        for (int cur : order) {
            if (dp[cur] == NEG_INF) continue;
            for (int[] nxt : g.get(cur)) {
                dp[nxt[0]] = Math.max(dp[nxt[0]], dp[cur] + nxt[1]);
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        int[][] edges = {{1,2,3}, {1,3,2}, {2,4,4}, {3,4,1}};
        long[] dp = longestPathDag(4, edges, 1);
        System.out.println(Arrays.toString(Arrays.copyOfRange(dp, 1, 5)));
    }
}

main.py

from collections import defaultdict, deque

def longest_path_dag(n, edges, start):
    g = defaultdict(list)
    indeg = [0] * (n + 1)

    for u, v, w in edges:
        g[u].append((v, w))
        indeg[v] += 1

    q = deque([i for i in range(1, n + 1) if indeg[i] == 0])
    order = []
    while q:
        cur = q.popleft()
        order.append(cur)
        for nxt, _ in g[cur]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)

    if len(order) != n:
        return None  # cycle

    NEG_INF = -10**18
    dp = [NEG_INF] * (n + 1)
    dp[start] = 0

    for cur in order:
        if dp[cur] == NEG_INF:
            continue
        for nxt, w in g[cur]:
            dp[nxt] = max(dp[nxt], dp[cur] + w)

    return dp

edges = [(1,2,3), (1,3,2), (2,4,4), (3,4,1)]
print(longest_path_dag(4, edges, 1)[1:])  # [0, 3, 2, 7]

main.rs

use std::collections::VecDeque;

fn longest_path_dag(n: usize, edges: &[(usize, usize, i64)], start: usize) -> Option<Vec<i64>> {
    let mut g = vec![Vec::<(usize, i64)>::new(); n + 1];
    let mut indeg = vec![0usize; n + 1];
    for &(u, v, w) in edges {
        g[u].push((v, w));
        indeg[v] += 1;
    }

    let mut q = VecDeque::new();
    for i in 1..=n {
        if indeg[i] == 0 {
            q.push_back(i);
        }
    }
    let mut order = Vec::new();
    while let Some(cur) = q.pop_front() {
        order.push(cur);
        for &(nxt, _) in &g[cur] {
            indeg[nxt] -= 1;
            if indeg[nxt] == 0 {
                q.push_back(nxt);
            }
        }
    }
    if order.len() != n {
        return None;
    }

    let neg_inf = -(1_i64 << 60);
    let mut dp = vec![neg_inf; n + 1];
    dp[start] = 0;
    for cur in order {
        if dp[cur] == neg_inf {
            continue;
        }
        for &(nxt, w) in &g[cur] {
            dp[nxt] = dp[nxt].max(dp[cur] + w);
        }
    }
    Some(dp)
}

fn main() {
    let edges = vec![(1, 2, 3), (1, 3, 2), (2, 4, 4), (3, 4, 1)];
    if let Some(dp) = longest_path_dag(4, &edges, 1) {
        println!("{:?}", &dp[1..=4]);
    } else {
        println!("cycle");
    }
}

위상 정렬/DAG DP 동작 완화 단계 추적

위상 순서가 고정되면 역참조 없이 전이가 가능합니다.
최장 경로는 max 전이를, 최단 경로는 min 전이를 사용하면 됩니다(사이클 없음 전제).
도달 불가 상태를 NEG_INF로 두는 초기화 정책이 핵심입니다.

평균 시간복잡도: 위상 정렬 + DP 전이 합쳐서 O(V + E)
공간복잡도: O(V + E)

DAG: 경로 수 세기

문제 의도: DAG에서 시작 정점부터 각 정점까지의 경로 수를 누적 계산합니다.
입력 예시: edges=[(1,2),(1,3),(2,4),(3,4)], start=1
출력 예시: 경로 수 배열(예: ways[4]=2)

main.cpp

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

vector<long long> countPathsDag(int n, const vector<pair<int, int>>& edges, int start) {
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        g[u].push_back(v);
        indeg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) if (indeg[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        order.push_back(cur);
        for (int nxt : g[cur]) {
            indeg[nxt]--;
            if (indeg[nxt] == 0) q.push(nxt);
        }
    }
    if ((int)order.size() != n) return {};

    vector<long long> ways(n + 1, 0);
    ways[start] = 1;
    for (int cur : order) {
        for (int nxt : g[cur]) ways[nxt] += ways[cur];
    }
    return ways;
}

int main() {
    auto ways = countPathsDag(4, {{1, 2}, {1, 3}, {2, 4}, {3, 4}}, 1);
    for (int i = 1; i <= 4; ++i) cout << ways[i] << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.*;

public class Main {
    static long[] countPathsDag(int n, int[][] edges, int start) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
        int[] indeg = new int[n + 1];
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            g.get(u).add(v);
            indeg[v]++;
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.offer(i);
        List<Integer> order = new ArrayList<>();
        while (!q.isEmpty()) {
            int cur = q.poll();
            order.add(cur);
            for (int nxt : g.get(cur)) {
                indeg[nxt]--;
                if (indeg[nxt] == 0) q.offer(nxt);
            }
        }
        if (order.size() != n) return null;

        long[] ways = new long[n + 1];
        ways[start] = 1;
        for (int cur : order) {
            for (int nxt : g.get(cur)) {
                ways[nxt] += ways[cur];
            }
        }
        return ways;
    }

    public static void main(String[] args) {
        long[] ways = countPathsDag(4, new int[][]{{1,2},{1,3},{2,4},{3,4}}, 1);
        System.out.println(Arrays.toString(Arrays.copyOfRange(ways, 1, 5)));
    }
}

main.py

from collections import defaultdict, deque

def count_paths_dag(n, edges, start):
    g = defaultdict(list)
    indeg = [0] * (n + 1)

    for u, v in edges:
        g[u].append(v)
        indeg[v] += 1

    q = deque([i for i in range(1, n + 1) if indeg[i] == 0])
    order = []
    while q:
        cur = q.popleft()
        order.append(cur)
        for nxt in g[cur]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)

    if len(order) != n:
        return None

    ways = [0] * (n + 1)
    ways[start] = 1

    for cur in order:
        for nxt in g[cur]:
            ways[nxt] += ways[cur]

    return ways

print(count_paths_dag(4, [(1,2), (1,3), (2,4), (3,4)], 1)[1:])
# [1, 1, 1, 2]

main.rs

use std::collections::VecDeque;

fn count_paths_dag(n: usize, edges: &[(usize, usize)], start: usize) -> Option<Vec<i64>> {
    let mut g = vec![Vec::<usize>::new(); n + 1];
    let mut indeg = vec![0usize; n + 1];
    for &(u, v) in edges {
        g[u].push(v);
        indeg[v] += 1;
    }

    let mut q = VecDeque::new();
    for i in 1..=n {
        if indeg[i] == 0 {
            q.push_back(i);
        }
    }

    let mut order = Vec::new();
    while let Some(cur) = q.pop_front() {
        order.push(cur);
        for &nxt in &g[cur] {
            indeg[nxt] -= 1;
            if indeg[nxt] == 0 {
                q.push_back(nxt);
            }
        }
    }

    if order.len() != n {
        return None;
    }

    let mut ways = vec![0_i64; n + 1];
    ways[start] = 1;
    for cur in order {
        for &nxt in &g[cur] {
            ways[nxt] += ways[cur];
        }
    }
    Some(ways)
}

fn main() {
    if let Some(ways) = count_paths_dag(4, &[(1, 2), (1, 3), (2, 4), (3, 4)], 1) {
        println!("{:?}", &ways[1..=4]);
    } else {
        println!("cycle");
    }
}