[BOJ 2252] 줄 세우기 (Java)

BOJ 2252 줄 세우기

난이도 : 골드 3

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

2252번: 줄 세우기

 

전략

문제 이름만 봤을 때는 7568 덩치 랑 비슷해보이지만, 자세히 읽어보면 그래프 문제라는 것을 알 수 있다.

 

일부 학생들에 대해서만 키 비교가 있고 이에 따라 순서가 정해지므로 방향 그래프인데

 

물리적인 키를 서로 비교한 것이기 때문에 사이클이 생길 수 없는 조건이다.

 

이는 위상 정렬로 간단하게 풀 수 있다.

 

노드 기준으로 들어오는 간선의 개수를 linked라고 했을 때

1. linked가 0인 노드들을 모두 큐에 넣는다.

2. 큐에서 노드를 제거(방문)하고 연결된 노드들의 linked를 감소시킨다.

3. linked가 0이 된 노드들을 큐에 삽입한다.

4. 2 ~ 3을 반복한다.

 

만약 N만큼의 반복이 이루어지지 않은 (모든 노드를 방문하지 않은) 상태에서 큐가 비었다면

사이클이 있는 그래프로 위상정렬을 할 수 없다.

하지만 문제 조건에 의해서 사이클이 없는 입력만 주어지므로 검사를 하지 않도록 구현하였다.

 

시간 복잡도는 O(N + M)이 된다.

 

시행착오

시행 착오는 없었다.

 

코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

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(topologicalSort(nodes));
        br.close();
    }

    static StringBuilder topologicalSort(final Node[] nodes) {
        StringBuilder sb = new StringBuilder();
        Queue<Node> queue = new LinkedList<>();

        for (int i = 1; i <= N; i++) {
            if (nodes[i].linked == 0)
                queue.offer(nodes[i]);
        }

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

            for (Node next : nodes[cur.num].link) {
                if (--next.linked == 0)
                    queue.add(next);
            }
        }

        return sb;
    }

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

        Node(int num) {
            this.num = num;
        }
    }
}

 

깨달은 점

위상 정렬을 처음 구현해봤는데, 단순하면서도 다양한 문제에서 유용하게 사용할 수 있을 것 같다.