백준 1766번 문제집 JAVA

링크텍스트

설명

문제를 풀기위해서는 위상정렬 알고리즘을 알아야한다. 위상정렬이란 순서가 정해져있는 작업을 차레로 수행해야할 때 그 순서를 결정해주기위해 사용하는 알고리즘이다.

while(!pq.isEmpty()) {
    int now = pq.poll(); // (1)
    sb.append(now).append(" "); // (2)
    for(int next : graph[now]) { // (3)
        inDegree[next]--; // (4)
        if(inDegree[next] == 0) { // (5)
            pq.offer(next); // (6)
        }
    }
}

📌 (1) int now = pq.poll();
우선순위 큐(pq)**에서 가장 작은 번호의 문제를 꺼냄.
pq에는 항상 진입 차수가 0인 문제들만 들어가 있음.
즉, 현재 풀어도 되는 문제 중에서 번호가 가장 작은 문제를 가져오는 것.

📌 (2) sb.append(now).append(" ");
now 값을 StringBuilder에 추가해서 출력할 결과를 저장.
문제 번호를 공백으로 구분하면서 나열.

📌 (3) for(int next : graph[now])
now 문제를 풀었으니, now 이후에 풀어야 하는 문제들(next)을 확인.

📌 (4) inDegree[next]--;
now를 풀었으니, now → next의 관계가 사라짐.
따라서 next 문제의 진입 차수를 1 감소시킴.

📌 (5) if(inDegree[next] == 0)
next 문제의 진입 차수가 0이 되었다면?
즉, next 문제를 풀기 위해 먼저 풀어야 할 선행 문제가 다 해결된 상태라면?

📌 (6) pq.offer(next);
이제 next 문제를 풀어도 되므로 우선순위 큐에 추가.
이렇게 하면 진입 차수가 0인 문제들 중에서 작은 번호부터 선택됨.

💡 정리 (위상 정렬 진행 방식)
진입 차수가 0인 문제부터 푼다.
푼 문제와 연결된 문제들의 진입 차수를 감소시킨다.
새롭게 진입 차수가 0이 된 문제를 우선순위 큐에 추가한다.
큐가 빌 때까지 반복한다.

시간복잡도: O((N + M) log N), 공간복잡도: O(N+M)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

class Main {
	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>[] graph = new ArrayList[n+1];
		int [] inDegree = new int[n+1];

		for(int i=1;i<=n;i++){
			graph[i] = new ArrayList<>();
		}

		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);
			inDegree[b]++;
		}

		PriorityQueue<Integer> pq = new PriorityQueue<>();

		for(int i=1;i<=n;i++){
			if(inDegree[i]==0){
				pq.offer(i);
			}
		}

		while(!pq.isEmpty()){
			int now = pq.poll();
			sb.append(now).append(" ");

			for(int next : graph[now]){
				inDegree[next]--;
				if(inDegree[next]==0){
					pq.offer(next);
				}
			}
		}
		System.out.print(sb);
	}
}

참고 글

https://m.blog.naver.com/ndb796/221236874984
https://loosie.tistory.com/247