[백준] 2252번. 줄 세우기(JAVA)

문제

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

---

풀이(30분)

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

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

        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] indegree = new int[N + 1];
        List<List<Integer>> edges = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            edges.add(new ArrayList<>());
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            indegree[B]++;
            edges.get(A).add(B);
        }

        List<Integer> answer = new ArrayList<>();

        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= N; i++){
            if(indegree[i] == 0){
                queue.add(i);
            }
        }

        while(!queue.isEmpty()){
            int cur = queue.poll();
            answer.add(cur);
            for(int next : edges.get(cur)){
                indegree[next]--;
                if(indegree[next] == 0){
                    queue.add(next);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i : answer){
            sb.append(i).append(" ");
        }

        System.out.println(sb);
    }

}

---

문제 풀이 전략

 

문제를 보고 고민하다가 특별한 알고리즘이 존재할 것 같아 살짝 검색을 해본 문제이다.

역시나 위상정렬이라는 확실한 아이디어가 있었고, 이를 공부하고 도입하여 해결할 수 있었다.

만약, 위상정렬에 대한 지식이 부족하다면 아래 링크를 참고하자.