[JAVA] 백준 1766 : 문제집

문제

1766번: 문제집

 

해결방법

위상 정렬의 대표적인 문제 중에 하나이다.

근래 위상정렬 문제를 꾸준히 풀어보고 있는데, 풀 때마다 헷갈려서 정리를 한 번 해두려고 한다.

 

일단 위상정렬은 Topological Sort 라고 부르며,

유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

쉽게 말하면 순서가 정해져있는 것들을 순서대로 나열하는 건데,

수학 2를 하기 전에 수학 1을 먼저 배워야 하고 그전에 기초수학을 배워야 하는데 이걸 배워야 하는 순서대로 정렬하는 것이다.

 

이 문제는 문제집에 문제들이 순서대로 주어지고, 먼저 푸는 것이 좋은 문제가 몇 개 주어진다.

그래서 먼저 푸는 것이 좋은 문제는 반드시 먼저 풀어야하는데, 그중에서도 쉬운 문제부터 풀어야 한다.

숫자가 낮을수록 쉬운 문제인데, 그렇기 때문에 진입 차수가 같다면 숫자가 낮은 순서부터 풀어야 한다.

이 부분을 정렬해주기 위해서 우선순위 큐를 사용한다.

 

자세한 내용은 코드의 주석을 참고하길 바란다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_G2_1766 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		// 인접리스트 작성
		ArrayList<Integer>[] list = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) list[i] = new ArrayList<>();
		
		// 진입 차수 배열
		int[] indegree = new int[N + 1];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			
			list[start].add(end); // 이 문제 다음에 풀어야할 문제를 이어줌
			indegree[end]++; // 진입 차수를 증가
		}
		
		// 위상정렬 파트,
		// 쉬운 문제 먼저하기위해 우선순위 큐 사용
		PriorityQueue<Integer> q = new PriorityQueue<>();
		
		// 진입 차수가 0인 것들을 넣음
		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) q.offer(i);
		}
		
		while (!q.isEmpty()) {
			int cur = q.poll();
			sb.append(cur + " "); // 현재 방문한 문제 출력
			
			// 현재 탐색 중인 문제 다음에 풀어야 되는 문제 확인
			for (Integer next : list[cur]) {
				indegree[next]--; // 진입 차수 감소
				
				// 진입 차수가 0이라면 큐에 넣음
				if (indegree[next] == 0) q.offer(next);
			}			
		}
		System.out.println(sb);
	}
}