[BOJ 1766] 문제집 (Java)

BOJ 1766 문제집

난이도 : 골드 2

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

1766번: 문제집

 

전략

위상정렬 문제이므로 문제집 순서를 그래프로 잘 표현해야 한다.

 

처음 접근했던 방법은 다음과 같다.

우선 입력을 바탕으로 방향 그래프를 생성한다. (그림에서 검은색 화살표)

 

그리고 노드 번호를 오름차순으로 탐색하면서 자신보다 높은 번호를 가진 노드를 가리키는 간선을 추가한다. (그림에서 파란색 화살표)

 

이 때 사이클이 생기지 않도록 해야한다.

이 방법에서의 문제점은 매번 사이클 여부를 확인해야 해서 매우 비효율적이라는 것이다.

 

그렇다면 추가적인 간선을 생성하지 않고 탐색하는 방법을 찾아야 한다.

 

입력된 그래프만으로 위상정렬을 수행한다면

4 -> 2, 3 -> 1  의 그래프에서 진입 차수가 0인 노드는 3, 4 두개이다.

즉, 큐에 동시에 여러 노드가 있어서 그 순서를 정해줘야 한다는 것이다.

 

이 경우에 문제의 조건에 따라 오름차순으로 정렬해야 하므로

큐를 노드 번호를 기준으로 하는 우선순위 큐로 변경하면 매우 간단하게 풀 수 있다.

 

시행착오

시행 착오는 딱히 없었다.

 

코드

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

public class Main {

    static int N, M;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        Node[] nodes = new Node[N + 1];
        for (int i = 1; i <= N; i++)
            nodes[i] = new Node(i);

        for (int i = 0; i < M; i++) {
            line = br.readLine().split(" ");
            int first = Integer.parseInt(line[0]);
            int second = Integer.parseInt(line[1]);
            nodes[first].link.add(nodes[second]);
            nodes[second].linked++;
        }

        System.out.println(topologySort(nodes));
    }

    static StringBuilder topologySort(final Node[] nodes) {
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.num - n2.num);
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if (nodes[i].linked == 0)
                pq.offer(nodes[i]);
        }

        for (int i = 0; i < N; i++) {
            Node cur = pq.poll();
            sb.append(cur.num + " ");

            for (Node next : cur.link) {
                if (--next.linked == 0)
                    pq.offer(next);
            }
        }
        return sb;
    }

    static class Node {
        int num;
        int linked = 0;
        ArrayList<Node> link = new ArrayList<>();
        Node(int num) {
            this.num = num;
        }
    }
}

 

깨달은 점

위상 정렬 문제를 풀 때 항상 그래프를 미리 완성하는 것이 최선이 아니라 큐 등의 정렬 수행 로직을 수정하는 방법에 대해서 생각해볼 수 있는 문제였다.