[백준] 2252 : 줄 세우기 - java [자바]

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

2252번: 줄 세우기

 

풀이

• "연결 정보가 주어진 N명의 학생 줄 세우기"는 다음과 같이 해석할 수 있다.
  => 연결 정보가 주어진 순환하지 않는 방향성 그래프(DAG=방향성 비순환 그래프)에서 각 노드를 줄 세우시오.
• 이를 구하는 방법은 위상정렬 알고리즘과 일치하므로 위상정렬 알고리즘을 이용해 풀이한다.
• 여기서는 각 노드의 연결 당한 정보를 linked 배열에 미리 입력 후 linked 배열이 0인 경우 해당 노드를 queue에 추가하여 BFS를 이용해 위상정렬 알고리즘을 구현했다.

1. 각 노드의 연결 당한 정보를 linked 배열에 저장한다.
2. linked 배열에서 값이 0인 노드를 queue에 추가한다.
3. 여기서부터는 BFS를 이용해 탐색하는데, queue에 노드를 추가하는 조건은 다음과 같다.
   1. queue에서 노드 하나를 꺼내고 정답 출력에 이용할 StringBuffer에 추가한다. 
   2. queue에서 꺼낸 현재 노드(current)와 연결된 노드(node)를 순회하며, linked[node]를 1씩 감소 시킨다.
   3. linked[node]가 0이 되었다면, queue에 추가하고 방문처리한다.
   4. 여기서 방문처리는 linked[node] == 0 인 경우로 처리한다.
4. StringBuffer에 담아둔 결과를 출력한다.

코드

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

public class 줄_세우기_2252 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        StringBuffer sb = new StringBuffer();

        List<List<Integer>> graph = new ArrayList<>();
        int[] linked = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            String[] input2 = br.readLine().split(" ");
            int start = Integer.parseInt(input2[0]);
            int target = Integer.parseInt(input2[1]);
            linked[target] += 1;
            graph.get(start).add(target);
        }


        Queue<Integer> queue = new LinkedList<>();

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

        while (!queue.isEmpty()) {
            Integer current = queue.poll();
            sb.append(current + " ");

            List<Integer> nodeList = graph.get(current);
            for (Integer node : nodeList) {
                if (--linked[node] == 0) {
                    queue.add(node);
                }
            }

        }

        bw.write(sb.toString());

        bw.close();
        br.close();
    }
}