[알고리즘] 백준 1766 문제집 - JAVA

www.acmicpc.net/problem/1766

1766번: 문제집

 

이전에 풀었던 문제와 마찬가지로 별 다른 응용 없이 위상정렬을 구현하는 문제이다.

 

다만 이 문제는 우선순위큐를 사용해야 한다.

 

문제에서 주어진 입력의 그래프를 그리면 아래와 같다.

 

일반 큐를 사용하여 위 그래프를 위상정렬 시키면 (물론 여러가지 경우가 있지만 반복문 돌아가는 순서대로 하면)

 

3 -> 4 -> 1 -> 2

 

위와 같은 순서로 정렬이 될텐데, 문제에서는 가능하다면 "작은" 숫자부터 출력하도록 요구하였다.

 

만약 우선순위 큐를 사용한다면 3 -> 1 -> 4 -> 2와 같이 출력을 할 수 있을 것이다.

 

# 우선순위큐 선언 (출처 : coding-factory.tistory.com/603)

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n;
    static int m;
    static int[] degree;
    static List<Integer>[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        list = new ArrayList[n + 1];
        degree = new int[n + 1];

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

        for (int i = 0; i < m; i++) {
            s = br.readLine();
            st = new StringTokenizer(s, " ");

            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            list[x].add(y);
            degree[y]++;
        }

        topologySort();
    }

    static void topologySort() {
        PriorityQueue<Integer> queue = new PriorityQueue<>();

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

        while (!queue.isEmpty()) {
            int current = queue.poll();
            System.out.print(current + " ");

            for (int i = 0; i < list[current].size(); i++) {
                int next = list[current].get(i);
                degree[next]--;

                if (degree[next] == 0) {
                    queue.add(next);
                }
            }
        }
    }
}

위상정렬 그 자체 내용이므로 코드 설명은 생략하도록 한다. 

 

이해가 되지 않는다면 위상정렬에 대한 내용을 복습해보자.