[BOJ] 백준 1766 - 문제집 풀이

1. 문제

https://www.acmicpc.net/problem/1766

1766번: 문제집

 

2. 풀이

• 위상 정렬 문제이다.
• 위상 정렬이 어떤 알고리즘인지 모르거나 혹은 알고 있는데 헷갈리다면 아래 문제를 먼저 풀어보고 이 문제를 보는 것도 좋다.
• https://sorryday.tistory.com/76

[BOJ] 백준 2623 - 음악프로그램 풀이

• 이 문제의 핵심은 문제에서 주어진 마지막 조건인 "가능한 쉬운 문제부터 풀어야 한다" 이다.
• 위상 정렬을 할 경우 큐에 진입 차수가 0이 되는 노드를 집어 넣어 사이클이 만들어지지 않는 그래프를 정렬한다
• 하지만 노드의 순서가 중요하거나 노드 안에 value가 있어서 이 value가 정렬의 기준이 된다면, 일반적인 큐에서는 값을 넣을 때마다 정렬을 해줘야 한다.
• 이를 쉽게 하기 위해 많이 써온 PriorityQueue, 우선 순위 큐를 사용한다.
• 일반적인 위상 정렬에서 기본 큐를 사용하는 것이 아닌 우선 순위 큐로 대체한 것이라고 이해하면 쉽다.
• 주요 자료구조
  • List<Integer>[] subjectList : 인접 리스트
  • List<Integer> result: 결과 리스트
  • int[] inDegree : 정점들의 진입 차수를 담은 배열
• 입력을 보면 둘째 줄부터 문제 번호의 순서쌍이 주어지는데, 앞 번호를 뒷 번호 보다 먼저 풀어야 한다.
• 즉 앞 번호가 뒷 번호의 부모가 되는 것이다.
• 이를 이용하여 인접 리스트를 만들 수 있고 진입 차수를 구할 수 있다.
• subjectOrderBFS()에서 일반 큐 대신 오름차순 정렬하는 우선 순위 큐를 이용하면 큐에 값을 add할 때 작은 값이 루트로 오도록 정렬해주기 때문에 문제에서 제시한 "가능한 쉬운 문제부터 풀어야 한다" 를 만족할 수 있다.
  
  
  

3. 코드

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

import org.omg.CORBA.PolicyListHelper;

import java.lang.*;
import java.security.Signature;
import java.sql.Array;

public class Main {
	static int N, M; // N : 문제 수, M : 좋은 문제에 대한 정보의 개수
	static int[] inDegree; // 진입 차수 배열
	static List<Integer>[] subjectList; // 인접 리스트
	static List<Integer> resultList; // 결과 리스트
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// 인접리스트 초기화
		subjectList = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			subjectList[i] = new ArrayList<Integer>();
		}
		
		// 인접정보 입력받기
		inDegree = new int[N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			subjectList[from].add(to);
			inDegree[to]++;
		}
		
		// 결과 리스트 초기화
		resultList = new ArrayList<Integer>();
		
		// 위상 정렬을 위한 BFS
		subjectOrderBFS();
		
		// 결과 출력
		for (int i = 0; i < resultList.size(); i++) {
			bw.write(resultList.get(i) + " ");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	private static void subjectOrderBFS() {
		// 가능한 쉬운 문제부터 풀어야한다고 했으므로 오름차순으로 정렬하고 뽑아야 한다.
		PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});
		
		// 진입 차수가 0인 노드를 q에 집어넣기
		for (int i = 1; i < inDegree.length; i++) {
			if (inDegree[i] == 0) {
				pq.add(i);
			}
		}
		
		// pq가 비어있을 때까지 bfs 실행
		while (!pq.isEmpty()) {
			int poll = pq.poll();
			resultList.add(poll);
			
			// 인접 정보 확인하기.
			for (int i = 0; i < subjectList[poll].size(); i++) {
				if (subjectList[poll].get(i) != null && --inDegree[subjectList[poll].get(i)] == 0) {
					pq.add(subjectList[poll].get(i));
				}
			}
		}
	}
}

4. 배운점

• 큐를 사용하는 알고리즘들은 조건이 다양하다면 우선 순위 큐를 한번쯤은 생각해보자.

 

5. 점수

• 90/100