[백준/JAVA] 1766_문제집

백준🔗

1766번: 문제집

 

 

문제

 

 

간단 풀이

어제에 이어 위상정렬 문제이다. 

약간의 차이점이 있다면 '3. 가능하면 쉬운 문제부터 풀어야 한다'라는 조건 때문에  기본 Queue나 Stack이 아닌 우선순위큐를 사용해야 했다. 

보통의 위상정렬 문제들은 선후 관계의 조건만 만족하면 되기 때문에 답이 여러가지 나올 수 있었는데, 이번 문제는 3번 조건으로 인해 답이 하나로 정해진다. 

위상 정렬은 풀이 방법만 알고 있으면 쉽게 풀리는 것 같다! 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 문제 개수
		int M = Integer.parseInt(st.nextToken()); // 문제 선후관계에 대한 정보 개수

		List<Integer>[] graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}
		int[] inDegree = new int[N + 1]; // 진입차수

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			graph[A].add(B); // A를 B보다 먼저 풀어야 함
			inDegree[B]++; // B의 진입차수 증가
		}

		// 우선순위 큐 -> 난이도 낮은 문제가 앞으로 오도록 정렬
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		// 우선 진입차수 0인 정점(문제)들 큐에 넣기
		for (int i = 1; i <= N; i++) {
			if (inDegree[i] == 0) {
				pq.add(i);
			}
		}

		while (!pq.isEmpty()) {
			int cur = pq.poll();
			bw.write(cur + " "); // 결과로 출력
			for (int x : graph[cur]) {
				inDegree[x]--; // 문제 하나 해결했으니 진입차수 감소
				if (inDegree[x] == 0) { // 선행 문제 모두 해결하면 큐에 넣기
					pq.add(x);
				}
			}
		}
		
		bw.flush();
		br.close();
		bw.close();
	}
}

 

참고 자료

[백준/JAVA] 2623_음악프로그램