[Java] 백준 BOJ / 2252번: 줄 세우기

줄 세우기

문제

---

문제 설명

N명의 학생 중에서 일부 학생들을 뽑아서 M번 비교한 결과가 주어진다.

결과를 보고 비교한 결과에 맞게 줄을 세운 결과를 출력하는 문제이다.

---

구현

며칠 전에 푼 한 줄로 서기 문제랑 비슷한 문제인줄 알았는데 이번 문제는 나보다 큰 사람이 정확히 누구인지 주어지기 때문에 다르게 접근해야 했다.

처음보는 문제 같아서 풀이를 참고 하였는데 위상정렬 알고리즘을 사용해야 한다.

위상정렬 알고리즘은 사이클이 없는 방향 그래프에서 작업 순서를 결정할 때 사용한다.

간단하게 개념을 말하면 진입 차수를 저장하는 배열을 선언한다. 이 진입 차수는 어떤 노드로 들어오는 간선의 수를 저장한다.

진입 차수가 0인 노드라면, 선행 조건이 없는 작업이므로 바로 수행한다.

매번 진입 차수가 0인 노드를 선택하고 그 노드와 연결된 간선들을 제거한 후에 새로운 진입 차수가 0인 노드를 갱신한다.

예제 입력이 들어왔다고 하면 그래프와 indegree 배열은 아래와 같다.

1: [3]
2: [3]
3: []

indegree[1] = 0
indegree[2] = 0
indegree[3] = 2

이 상태에서 indegree가 0이라면 Queue에 넣는다.

그러면 큐의 초기상태는 1, 2 이다.

1. 큐에서 1을 꺼낸 후 바로 출력한다. 결과 : 1
   그 후 1의 뒤에 오는 3의 진입 차수를 줄인다.
   indegree[3] = 1
   
   

2. 큐에서 2를 꺼낸 후 바로 출력한다. 결과 : 1 2
   그 후 2의 뒤에 오는 3의 진입 차수를 줄인다.
   indegree[3] = 0 으로 진입차수가 0이 되었으니 Queue에 추가한다.

3. 큐에서 3을 꺼낸 후 바로 출력한다. 결과 1 2 3

이런 식으로 동작하면 된다.

---

코드

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

public class Main_2252 {
    static int n, m;
    static ArrayList<Integer>[] list;
    static int[] indegree;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

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

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

            list[front].add(back);
            indegree[back]++;
        }

        topologicalSort();
    }

    public static void topologicalSort() {
        Queue<Integer> queue = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

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

        while (!queue.isEmpty()) {
            //들어오는 간선이 없는 경우 우선순위가 없으니 바로 출력
            int cur = queue.poll();
            sb.append(cur).append(" ");

            //현재 숫자보다 뒤에 와야 하는 숫자들을 탐색
            for (int next : list[cur]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        System.out.println(sb);
    }
}