[Java] 백준 1766번: 문제집

[문제 바로 가기] - 문제집

유형 : 위상정렬 + 우선순위 큐 + 그래프 탐색

💡 접근 방식

1. N개의 문제는 모두 풀어야 한다 - 그래프 탐색
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다 - 위상 정렬
3. 가능하면 쉬운 문제부터 풀어야 한다 - 우선순위 큐

이 문제는 위의 세 조건을 모두 만족해야 한다.
따라서 위상 정렬 + 우선순위 큐 + 그래프 탐색을 사용하는데, 위상 정렬은 익숙하지 않은 개념이라 SSAFY에서 배웠던 알고리즘 개념을 다시 찾아봤다.

위상 정렬(Topology Sort)이란!

• 유향 그래프(방향이 있는 그래프)의 정점들을 방향을 거스르지 않도록 나열하는 것
• 순서가 정해져 있는 작업들을 순서에 맞게 수행해야 할 때, 그 순서를 결정해주는 알고리즘
• 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있음
  (이 문제는 가능하면 쉬운 문제부터 풀이해야 하므로 하나의 답만 나온다)
• 위상 정렬이 성립하기 위해서는 반드시 사이클이 존재하지 않아야 함

이 문제는 먼저 푸는 것이 좋은 문제가 있는 유향 그래프다.

4 2
1 2
2 1

그리고 위와 같이 주어진다면 문제를 풀이할 수 없는 구조이므로 사이클이 존재하지 않는다. 따라서 위상 정렬 사용 가능!

1. 후행하는 노드들의 진입 차수를 구한다. (indegree 배열)
2. 인접 리스트에 선행하는 노드 -> 후행하는 노드를 넣는다. (방향이 있기 때문에)

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
		
			indegree[n2]++;
			list[n1].add(n2);
		}

3. 진입 차수가 0인 (indegree[i] == 0인) 노드들을 우선순위 큐에 넣는다.

		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) queue.add(i);
		}

4. BFS로 쉬운 문제 순서대로 그래프 탐색을 하면서 해당 문제의 후행하는 문제의 진입 차수를 하나씩 빼준다.
   이때, 진입 차수가 0이 된 노드를 우선순위 큐에 넣는다.

		while (!queue.isEmpty()) {
			int cur = queue.poll();
			sb.append(cur + " ");
			
			for (Integer node : list[cur]) {
				indegree[node]--;
				
				if (indegree[node] == 0) queue.add(node);
			}
		}

---

풀이

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

/**
 * 백준 1766번 문제집
 * - 위상정렬 + 우선순위 큐 + 그래프 탐색
 */

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());
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int indegree[] = new int[N + 1];
		
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		List<Integer>[] list = new ArrayList[N + 1];
		
		for (int i = 0; i <= N; i++) {
			list[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
		
			indegree[n2]++;
			list[n1].add(n2);
		}
		
		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) queue.add(i);
		}
		
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			sb.append(cur + " ");
			
			for (Integer node : list[cur]) {
				indegree[node]--;
				
				if (indegree[node] == 0) queue.add(node);
			}
		}
		
		System.out.println(sb);
	}
}