동적 계획법그래프(인접 목록)위상 정렬P0154

물이 흘러가는 방법의 수

논에 물을 대는 칸 n개에 1번부터 n번까지 번호가 붙어 있다. 칸 사이에는 물길 m개가 있다. 물길 하나 "a b"는 물이 a번 칸에서 b번 칸으로만 흐른다는 뜻이다. 같은 두 칸 사이에 물길이 여럿 있을 수 있으며, 서로 다른 물길은 같은 두 칸을 이어도 다른 물길로 친다. 어떤 칸에서 물길을 따라 흘러도 다시 그 칸으로 돌아오는 일은 없다. 1번 칸(샘)에 물을 부으면, 물은 지금 있는 칸에서 나가는 물길 가운데 하나를 골라 흘러가기를 되풀이하다가, 나가는 물길이 없는 칸에 닿으면 그 칸에 고여 멈춘다. 물이 흘러갈 수 있는 방법이 모두 몇 가지인지 구하라. 지나는 물길의 차례가 다르면 다른 방법으로 센다. 1번 칸에서 나가는 물길이 없으면 물은 1번 칸에 그대로 고이며, 이것도 한 가지 방법이다. 수가 아주 클 수 있으니 1,000,000,007로 나눈 나머지를 출력한다.

입력: 첫 줄에 n과 m, 다음 m줄에 줄마다 a와 b가 빈칸으로 나뉘어 주어진다.
1 ≤ n ≤ 10,000, 0 ≤ m ≤ 10,000, 1 ≤ a, b ≤ n, a ≠ b.
물길을 따라 돌아오는 고리는 없다.
출력: 흘러가는 방법의 수를 1,000,000,007로 나눈 나머지

예시 1 · stdin

stdout

예시 2 · stdin

stdout

예시 3 · stdin

3 0

stdout

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

ways[v] = '1번에서 v까지 흘러오는 방법의 수'라 하면, v로 들어오는 물길마다 그 출발 칸의 ways를 더하면 돼요(동적 계획법).
답은 나가는 물길이 없는 칸(물이 고이는 칸)마다 ways를 더한 값이에요 — 1번 칸에서 나가는 물길이 없으면 1번도 그런 칸이라 ways[1] = 1이 그대로 답이 돼요(셋째 예시).
다만 더하기 전에 출발 칸의 값이 다 끝나 있어야 하니, 들어오는 물길이 모두 계산된 칸부터 꺼내는 위상 정렬(칸 알고리즘 — inflow를 세고 0이 된 칸을 큐에 넣어요) 차례로 흘려 보내요.
함정 하나: 큐에 1번만 넣고 시작하면, 1번에서 못 가는 칸(둘째 예시의 6번)에서 들어오는 물길이 inflow에 남아 그 아래 칸이 영영 꺼내지지 않아요 — 들어오는 물길이 없는 칸을 모두 넣어요(그 칸들의 ways는 0이라 답은 바뀌지 않아요).
함정 둘: 번호 순서대로 흘려 보내면 틀려요 — 번호가 작은 칸이 위에 있다는 약속이 없어요.
함정 셋: 물을 붓는 1번 칸을 고이는 칸에서 빼면 셋째 예시에서 0이 나와요.
함정 넷: 방법의 수는 2^2500처럼 커져요.
더할 때마다 나머지를 구해야 해요: C·C++의 long long도 마지막에 한 번만 나누면 넘치고, Python은 넘치지 않지만 나누지 않으면 큰 수를 그대로 출력해요.
두 나머지의 합은 약 20억이라 32비트 int(약 21억)에 아슬아슬하게 들어가니, 넉넉하게 C·C++ long long, Java·C# long에 담고, JavaScript·TypeScript·크레이콘의 수는 2^53까지 정확해서 그대로 돼요.
함정 다섯: 재귀로 count(v)를 메모하며 세면 10,000칸 사슬에서 Python은 기본 재귀 한도(1,000)를 넘어 RecursionError가 나고, 크레이콘도 4,000단계쯤에서 멈춰요 — 큐로 도는 위상 정렬은 깊이가 없어요.
큐도 언어마다 달라요: Python collections.deque, Java ArrayDeque<Integer>, C# Queue<int>, C++ std::queue<int>, C 배열과 앞·뒤 자리, JavaScript·TypeScript·크레이콘은 목록에 넣기만 하고 앞 자리(head)를 옮겨요(shift()는 매번 당겨서 느려요).
크레이콘은 목록이 10,000칸까지라 번호에서 1을 빼 0번부터 둬요(새목록(n, 0)).

Pythonmain.py · 32 줄

import sysfrom collections import deque MOD = 1_000_000_007data = sys.stdin.read().split()n, m = int(data[0]), int(data[1]) down = [[] for _ in range(n + 1)]  # down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)inflow = [0] * (n + 1)  # 아직 계산하지 않은, 들어오는 물길의 수for i in range(m):    a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])    down[a].append(b)    inflow[b] += 1 # 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 차례로 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)ways = [0] * (n + 1)  # ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1ready = deque(v for v in range(1, n + 1) if inflow[v] == 0)while ready:    v = ready.popleft()    for nxt in down[v]:        ways[nxt] = (ways[nxt] + ways[v]) % MOD        inflow[nxt] -= 1        if inflow[nxt] == 0:            ready.append(nxt) # 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다total = 0for v in range(1, n + 1):    if not down[v]:        total = (total + ways[v]) % MODprint(total)

JavaScriptmain.js · 28 줄

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const MOD = 1000000007; const down = Array.from({ length: n + 1 }, () => []); // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)const inflow = new Array(n + 1).fill(0); // 아직 계산하지 않은, 들어오는 물길의 수for (let i = 0; i < m; i++) {  const a = data[2 + 2 * i], b = data[3 + 2 * i];  down[a].push(b);  inflow[b]++;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)const ways = new Array(n + 1).fill(0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1;const queue = [];for (let v = 1; v <= n; v++) if (inflow[v] === 0) queue.push(v);for (let head = 0; head < queue.length; head++) {  const v = queue[head];  for (const next of down[v]) {    ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다    if (--inflow[next] === 0) queue.push(next);  }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다let total = 0;for (let v = 1; v <= n; v++) if (down[v].length === 0) total = (total + ways[v]) % MOD;console.log(total);

TypeScriptmain.ts · 30 줄

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const MOD = 1000000007; const down: number[][] = Array.from({ length: n + 1 }, (): number[] => []); // down[a] = a에서 물이 흘러가는 칸들const inflow: number[] = new Array<number>(n + 1).fill(0); // 아직 계산하지 않은, 들어오는 물길의 수for (let i = 0; i < m; i++) {  const a = data[2 + 2 * i], b = data[3 + 2 * i];  down[a].push(b);  inflow[b]++;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)const ways: number[] = new Array<number>(n + 1).fill(0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[1] = 1;const queue: number[] = [];for (let v = 1; v <= n; v++) if (inflow[v] === 0) queue.push(v);for (let head = 0; head < queue.length; head++) {  const v = queue[head];  for (const next of down[v]) {    ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다    if (--inflow[next] === 0) queue.push(next);  }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다let total = 0;for (let v = 1; v <= n; v++) if (down[v].length === 0) total = (total + ways[v]) % MOD;console.log(total);

JavaMain.java · 46 줄

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer; public class Main {    static final int MOD = 1_000_000_007;     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(in.readLine());        int n = Integer.parseInt(st.nextToken());        int m = Integer.parseInt(st.nextToken());         List<List<Integer>> down = new ArrayList<>(); // down.get(a) = a에서 물이 흘러가는 칸들        for (int v = 0; v <= n; v++) down.add(new ArrayList<>());        int[] inflow = new int[n + 1]; // 아직 계산하지 않은, 들어오는 물길의 수        for (int i = 0; i < m; i++) {            st = new StringTokenizer(in.readLine());            int a = Integer.parseInt(st.nextToken());            int b = Integer.parseInt(st.nextToken());            down.get(a).add(b);            inflow[b]++;        }         // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)        long[] ways = new long[n + 1]; // 두 나머지의 합은 int를 넘을 수 있어 long        ways[1] = 1;        ArrayDeque<Integer> ready = new ArrayDeque<>();        for (int v = 1; v <= n; v++) if (inflow[v] == 0) ready.add(v);        while (!ready.isEmpty()) {            int v = ready.poll();            for (int next : down.get(v)) {                ways[next] = (ways[next] + ways[v]) % MOD;                if (--inflow[next] == 0) ready.add(next);            }        }        // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다        long total = 0;        for (int v = 1; v <= n; v++) if (down.get(v).isEmpty()) total = (total + ways[v]) % MOD;        System.out.println(total);    }}

C#Main.cs · 44 줄

using System;using System.Collections.Generic; class Program{    const long MOD = 1_000_000_007;     static void Main()    {        string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(first[0]);        int m = int.Parse(first[1]);         var down = new List<int>[n + 1]; // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)        for (int v = 0; v <= n; v++) down[v] = new List<int>();        var inflow = new int[n + 1]; // 아직 계산하지 않은, 들어오는 물길의 수        for (int i = 0; i < m; i++)        {            string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            int a = int.Parse(p[0]), b = int.Parse(p[1]);            down[a].Add(b);            inflow[b]++;        }         // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)        var ways = new long[n + 1]; // 두 나머지의 합은 int를 넘을 수 있어 long        ways[1] = 1;        var ready = new Queue<int>();        for (int v = 1; v <= n; v++) if (inflow[v] == 0) ready.Enqueue(v);        while (ready.Count > 0)        {            int v = ready.Dequeue();            foreach (int next in down[v])            {                ways[next] = (ways[next] + ways[v]) % MOD;                if (--inflow[next] == 0) ready.Enqueue(next);            }        }        // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다        long total = 0;        for (int v = 1; v <= n; v++) if (down[v].Count == 0) total = (total + ways[v]) % MOD;        Console.WriteLine(total);    }}

C++main.cpp · 40 줄

#include <iostream>#include <queue>#include <vector> int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    const long long MOD = 1000000007;    int n, m;    std::cin >> n >> m;     std::vector<std::vector<int>> down(n + 1); // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)    std::vector<int> inflow(n + 1, 0);         // 아직 계산하지 않은, 들어오는 물길의 수    for (int i = 0; i < m; i++) {        int a, b;        std::cin >> a >> b;        down[a].push_back(b);        inflow[b]++;    }     // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)    std::vector<long long> ways(n + 1, 0); // 두 나머지의 합은 int를 넘을 수 있어 long long    ways[1] = 1;    std::queue<int> ready;    for (int v = 1; v <= n; v++)        if (inflow[v] == 0) ready.push(v);    while (!ready.empty()) {        int v = ready.front();        ready.pop();        for (int next : down[v]) {            ways[next] = (ways[next] + ways[v]) % MOD;            if (--inflow[next] == 0) ready.push(next);        }    }    // 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다    long long total = 0;    for (int v = 1; v <= n; v++)        if (down[v].empty()) total = (total + ways[v]) % MOD;    std::cout << total << "\n";}

Cmain.c · 45 줄

#include <stdio.h> #define MAXN 10001#define MAXM 10000#define MOD 1000000007LL /* 인접 목록을 배열로: head[a]는 a에서 나가는 첫 물길 칸, next[e]는 다음 칸(-1이면 끝) */static int head[MAXN], next[MAXM], to[MAXM];static int inflow[MAXN];  /* 아직 계산하지 않은, 들어오는 물길의 수 */static long long ways[MAXN]; /* 두 나머지의 합은 int를 넘을 수 있어 long long */static int queue[MAXN]; int main(void) {    int n, m;    scanf("%d %d", &n, &m);    for (int v = 1; v <= n; v++) head[v] = -1;    for (int e = 0; e < m; e++) {        int a, b;        scanf("%d %d", &a, &b);        to[e] = b;        next[e] = head[a];        head[a] = e;        inflow[b]++;    }     /* 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다) */    ways[1] = 1;    int qh = 0, qt = 0;    for (int v = 1; v <= n; v++)        if (inflow[v] == 0) queue[qt++] = v;    while (qh < qt) {        int v = queue[qh++];        for (int e = head[v]; e != -1; e = next[e]) {            int b = to[e];            ways[b] = (ways[b] + ways[v]) % MOD;            if (--inflow[b] == 0) queue[qt++] = b;        }    }    /* 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다 */    long long total = 0;    for (int v = 1; v <= n; v++)        if (head[v] == -1) total = (total + ways[v]) % MOD;    printf("%lld\n", total);    return 0;}

Craykonmain.cray · 53 줄

MOD = 1000000007;첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1]; // 목록은 10,000칸까지라 칸 번호에서 1을 빼 0번부터 둔다down = []; // down[a] = a에서 물이 흘러가는 칸들(물길마다 한 번씩)반복 (v = 0; v < n; v++){    down.넣기([]);}inflow = 새목록(n, 0); // 아직 계산하지 않은, 들어오는 물길의 수반복 (i = 0; i < m; i++){    물길 = 콘솔.수들읽기();    down[물길[0] - 1].넣기(물길[1] - 1);    inflow[물길[1] - 1] += 1;} // 위상 정렬: 들어오는 물길이 모두 계산된 칸부터 꺼낸다(1번에서 못 가는 칸도 모두 넣는다)ways = 새목록(n, 0); // ways[v] = 1번에서 v까지 흐르는 방법의 수(MOD로 나눈 나머지)ways[0] = 1;queue = [];반복 (v = 0; v < n; v++){    만약 (inflow[v] == 0)    {        queue.넣기(v);    }}반복 (head = 0; head < queue.개수; head++){    v = queue[head];    각각 (next 에서 down[v])    {        ways[next] = (ways[next] + ways[v]) % MOD; // 두 수 모두 MOD보다 작아 합이 2^53보다 훨씬 작다        inflow[next] -= 1;        만약 (inflow[next] == 0)        {            queue.넣기(next);        }    }}// 물은 나가는 물길이 없는 칸에 고여 멈춘다: 그런 칸마다 그 칸까지 오는 길의 수를 더한다total = 0;반복 (v = 0; v < n; v++){    만약 (down[v].개수 == 0)    {        total = (total + ways[v]) % MOD;    }}콘솔.쓰기(total);