Baekjoon | Q.1766 - 문제집

1766번: 문제집

 우선순위가 정해진 문제를 푸는 순서를 찾아내는 문제이다. 문제를 푸는 순서에 대한 조건은 두 가지가 있다.

 

1. 순서가 정해진 문제는 순서에 맞춰 풀어야 한다.                                          ---- 위상정렬

2. 가능한 쉬운 문제(문제 번호가 낮은 문제) 먼저 풀어야 한다.                     ---- 우선순위 큐

 

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    StringBuilder sb = new StringBuilder();
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    
    ArrayList<Integer> li[] = new ArrayList[N + 1]; // 간선 정보 저장
    for (int i = 0; i < li.length; i++) {
      li[i] = new ArrayList<Integer>();
    }
    int[] indegree = new int[N + 1];  // 진입차수 기록
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    
    for (int i = 0; i < M; i++) {
      int from = sc.nextInt();
      int to = sc.nextInt();
      
      li[from].add(to);
      indegree[to]++;
    }

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

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

      for (int i = 0; i < li[now].size(); i++) {
        int next = li[now].get(i);
        indegree[next]--;
        if(indegree[next] == 0) queue.add(next);
      }
    }

    System.out.println(sb.toString());
    sc.close();
    
  }
}

 

 위상정렬은 순서가 정해져 있는 작업을 차례로 수행할 때 그 순서를 결정하기 위해 사용하는 알고리즘이다. 구현 순서는 다음과 같다.

 

0. 제일 먼저 진입 차수가 0인 문제 큐에 추가 (아무런 선행 조건이 없는 문제부터)

1. 큐에 저장된 문제를 하나 꺼내서 푼다.

2.  풀어낸 문제와 연결된 문제를 찾아 선행 문제를 해결했으므로 진입 차수를 하나 낮춘다.

3. 만약 진입 차수가 0이라면(선행 문제를 모두 해결한 경우) 큐 대기열에 추가

4. 큐가 빌 때 까지 1 ~ 3번 반복

 

 여기서 쉬운 문제인 번호가 낮은 문제부터 풀어야 하므로 큐를 우선순위 큐로 생성해준다면 모든 조건을 만족하는 문제 풀이 순서를 찾을 수 있다.