[백준] 31445번: 부분 달리기 시합

문제

백준 - 31445번: 부분 달리기 시합

분석

N명의 사람이 달리기 시합을 하고 M개의 상대적인 실력 정보가 주어질 때, 모든 사람의 순위를 정확하게 예상할 수 있도록 뽑는 경우의 수를 구하는 문제이다.

그래프를 구성하고 위상정렬 알고리즘을 사용하여 degree가 0인 값부터 경우의 수를 구한다. 이 경우의 수가 모든 노드에 전파되어야 하는데, 같은 곳을 중복해서 전파하면 안된다. 따라서 subQ를 통해 bfs를 구현한다. 이때 방문처리를 하기 때문에 중복 계산을 방지한다.

각 노드마다 최대 M개 간선을 탐색할 수 있기 때문에 O(NxM)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static List<Integer>[] graph;
	static boolean[] visited;
	static int[] degree, cnt;
	static final int MOD = 1_000_000_007;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		graph = new List[N + 1];
		for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}
		visited = new boolean[N + 1];
		degree = new int[N + 1];
		cnt = new int[N + 1];
		Arrays.fill(cnt, 1);
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			graph[x].add(y);
			degree[y]++;
		}
		int answer = 0;
		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			if (degree[i] == 0) {
				q.add(i);
			}
		}

		while (!q.isEmpty()) {
			int node = q.poll();
			answer = (answer + cnt[node]) % MOD;

			Queue<Integer> subQ = new LinkedList<>();
			boolean[] visited = new boolean[N + 1];

			for (int next : graph[node]) {
				if (--degree[next] == 0) {
					q.add(next);
				}
				if (!visited[next]) {
					visited[next] = true;
					subQ.add(next);
				}
			}

			while (!subQ.isEmpty()) {
				int cur = subQ.poll();
				cnt[cur] = (cnt[cur] + cnt[node]) % MOD;

				for (int next : graph[cur]) {
					if (!visited[next]) {
						visited[next] = true;
						subQ.add(next);
					}
				}
			}
		}
		System.out.println(answer);
		br.close();
	}

}