문제

아이디어

문제 감이 잘 안잡혀서 알고리즘 분류를 확인한 후에 풀었다.
위상정렬에 대해서 학습해보고, 문제를 풀어보자.

위상 정렬 (Topological Sorting)

위상 정렬 은 정렬 알고리즘의 한 종류로, 방향 그래프에서 정점들을 선형으로 정렬할 수 있다.
조금 더 정확히 말하자면 사이클이 존재하지 않는 방향 그래프를 선형으로 정렬하는 알고리즘 이다.

진입 차수와 진출 차수

진입 차수 (In-Degree)

특정 정점으로 들어오는 간선의 수를 나타냅니다. 즉, 다른 정점에서 해당 정점으로 향하는 간선의 개수를 의미합니다.

진출 차수 (Out-Degree)

특정 정점에서 나가는 간선의 수를 나타냅니다. 즉, 해당 정점에서 다른 정점으로 향하는 간선의 개수를 의미합니다.

위상 정렬 동작 과정

1. 모든 정점의 진입 차수를 계산합니다.
2. 진입 차수가 0인 정점을 큐에 추가합니다.
3. 큐에서 정점을 하나씩 꺼내고, 해당 정점과 연결된 간선을 제거합니다. 이때 새로운 진입 차수가 0이 되는 정점을 큐에 추가합니다.
4. 모든 정점을 처리할 때까지 이 과정을 반복합니다.

간단한 예시를 통해 위상 정렬에 대해서 조금 더 자세히 알아보자.

모든 정점의 진입 차수를 계산하고, 진입 차수가 0인 정점을 큐에 추가

진입 차수가 0인 노드는 A 하나만 존재한다.

큐에서 노드를 꺼내고 간선을 제거, 진입차수가 0이 된다면 큐에 추가

A는 큐에서 꺼내 정렬된 노드를 저장할 큐에 새로 저장해준다.

A의 간선이 제거된 후, B의 진입 차수가 0이 되었으므로 큐에 삽입해준다.

이를 큐가 빌 때까지 진행한다면 성공적으로 정렬을 진행할 수 있다.

소스코드

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

public class Main {
    static int n;
    static int m;
    static ArrayList<Integer>[] adj;
    static Node[] nodes;
    static Deque<Node> queue = new ArrayDeque<>();

    static class Node {
        int num;
        int inDegree;

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

    static void setQueue() {
        for (int i = 1; i < n + 1; i++) {
            if (nodes[i].inDegree == 0) {
                queue.addLast(nodes[i]);
                nodes[i] = null;
            }
        }
    }

    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());

        adj = new ArrayList[n + 1];
        nodes = new Node[n + 1];
        for (int i = 1; i < n + 1; i++) {
            adj[i] = new ArrayList<>();
            nodes[i] = new Node(i, 0);
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            adj[a].add(b);
            nodes[b].inDegree += 1;
        }

        setQueue();
        while(!queue.isEmpty()) {
            Node curNode = queue.removeFirst();

            bw.write(curNode.num + " ");
            for (Integer dest : adj[curNode.num]) {
                nodes[dest].inDegree -= 1;
                if(nodes[dest].inDegree == 0) {
                    queue.addLast(nodes[dest]);
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

채점 결과

위상 정렬을 알고 있다면 쉽게 풀 수 있었을 것 같다.