[백준][BOJ-1766][자바] 문제집

www.acmicpc.net/problem/1766

1766번: 문제집

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		StringBuilder result = new StringBuilder();
		int[] distance = new int[N+1];
		List<Integer>[] list = new List[N+1];
		
		for(int i=1; i<=N; i++) {
			list[i] = new ArrayList<>();
		}
		
		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);
			distance[end]++;
		}
		
		PriorityQueue<Data> pq = new PriorityQueue<>();
		// 진입 노드가 0인 노드들 pq에 집어 넣기 
		for(int i=1; i<=N; i++) {
			// 노드가 0이더라도 먼저 풀리는 문제 있을수 있으니깐 우선순위 1로 넣어준다.
			if(distance[i] == 0) pq.offer(new Data(i,1));
		}
		
		while(!pq.isEmpty()) {
			Data data = pq.poll();
			result.append(data.no+" ");
			
			//우선순위 조건에 의해 꺼내진 노드의 간선들 제거
			for(int i=0; i<list[data.no].size(); i++) {
				distance[list[data.no].get(i)]--;
				
				//제거 당한 노드들중에서 진입이 0인 경우 먼저 푸는 것이 좋은 문제에 해당해서 우선순위를 0으로 주었다.
				if(distance[list[data.no].get(i)] == 0) {
					pq.offer(new Data(list[data.no].get(i), 0));
				}
			}
		}
		
		System.out.println(result.toString());
	}
	
	static class Data implements Comparable<Data>{
		int no;
		int priorty;
		public Data(int no, int priorty) {
			super();
			this.no = no;
			this.priorty = priorty;
		}
		@Override
		public int compareTo(Data o) {
			// 조건 3번에 해당
			if(this.priorty == o.priorty) return this.no - o.no;
			// 조건 2번에 해당
			return this.priorty - o.priorty;
		}
	}
}

 

조건

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

정리

• 순서가 존재하므로 -> 위상정렬 , 조건이 존재 하므로 -> 우선순위 두 알고리즘의 혼합 문제이다.
• 먼저 우선순위의 조건을 설정해준다. 변수를 2개 주어서 조건 2번과 3번을 처리 해주었다.
• 위상정렬 알고리즘의 의해 진입 되는 간선이 없는 노드들을 우선순위 큐에 넣어주는데 조건 2번의 의해 priorty 변수의 값에 1을 주었다.
• 반복문을 돌리는데 '먼저 풀면 좋은 문제 중에, 쉬운 문제'를 뽑는다.
• 해당 노드가 연결하고 있는 간선을 다 제거한다.
• 0이 해당 되는 노드가 있다면 우선순위 큐에 넣어준다. 조건 2번의 의해 priorty 변수의 값에 0을 주었다.