BOJ_2252 : 줄 세우기

👉 문제링크

2252번: 줄 세우기

---

---

🔸 문제 분석 🔸

• N명의 학생들을 키 순서대로 줄을 세운다.
  • 모두의 키 정보가 주어지는 것이 아니라, 두 학생을 비교해서 누가 앞에 오는지에 대한 정보만 주어진다.
• 위상 정렬 알고리즘에 대한 간단한 문제이다.
  • 키가 큰 학생이 앞에 오는지, 작은 학생이 앞에 오는지에 대한 정보는 없고, 누가 앞으로 오느냐만 주어진다.
  • 따라서 답이 여러가지가 될 수 있으므로 서브테스크 문제이다.
  • BFS로 간단히 풀이할 수 있다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] in_cnt = new int[N + 1];
        ArrayList<Integer>[] out_list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            out_list[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int out = Integer.parseInt(st.nextToken());
            int in = Integer.parseInt(st.nextToken());
            in_cnt[in]++;
            out_list[out].add(in);
        }

        // BFS
        Queue<Integer> que = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            if (in_cnt[i] == 0)
                que.add(i);
        }

        StringBuilder sb = new StringBuilder();

        while (!que.isEmpty()) {
            int n = que.poll();
            sb.append(n).append(' ');

            for (int i : out_list[n]) {
                if (--in_cnt[i] == 0)
                    que.add(i);
            }
        }

        // Output
        sb.deleteCharAt(sb.length() - 1);
        System.out.print(sb);
    }
}

🔸 코드 해석 🔸

• M개의 키 순서는 단방향 그래프의 간선 정보이다.
  • 간선 정보를 out_list 에 저장한다.
    (노드에서 진출 방향 정보만 저장)
  • 이때, 각 노드의 진입 차수를 in_cnt 배열에서 카운트한다.
• 진입 차수가 0인 노드들을 큐의 초기값으로 넣는다. (이 중 아무 노드나 시작이 될 수 있다)
• 큐가 빌 때까지 계산을 반복한다.
  • 큐에서 노드 번호를 꺼내면  출력해준다.
  • 해당 번호와 연결 된 노드의 진입 차수 in_cnt를 -1 한다.
  • in_cnt 가 0이 된 경우엔 큐에 넣어준다.

---

🔸 end 🔸

• 문제를 보고 위상 정렬을 떠올렸지만, 알고리즘을 공부한 후 거의 풀어보지 않아서 알고리즘을 공부한 기록을 보고 구현했다.
• 막상 풀어보니 코드가 간단해서 다음엔 안보고 풀어낼 수 있을 것 같다.