[BOJ][Java] 2252번 줄 세우기

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/2252

 

이 문제에서는 출력 조건에 답이 여러 가지인 경우에는 아무거나 출력한다는 것을 보고

위상정렬 알고리즘을 사용한다는 것을 유추해 내면 이후에는 단순 알고리즘 구현문제로 바뀌게 된다.

 

먼저 위상정렬을 사용하려면 진입 차수에 대해 알아야 한다.

진입 차수란 그래프로 표현했을때 자신에게 들어오는 간선의 개수이다.

예제 입력 1번을 예로 살펴보면

d (진입 차수 배열), List (인접 리스트)로 표현할 수 있다.

 

이때 위상정렬 알고리즘을 사용하려면 아래와 같이 하면 된다.

Queue에는 진입 차수가 0인 정점들을 채워준다.

이후 q에서 하나씩 빼면서 해당 정점을 출력해주고

해당 정점과 인접한 정점의 진입 차수를 하나씩 빼준다. 

1번 예제에서는 1번과 인접한 정점이 3번 하나밖에 없으므로

3번의 진입 차수를 -- 해준다. 

여기서 만약 3번의 진입차수가 0이 된다면 큐에 추가하고,

0이 아니라면 큐에 추가하지 않는다.

 

이제 다시 큐에서 poll 하여 정점 2를 출력해 주고

2번 정점의 인접한 정점인 3번의 진입차수를 -- 해준다.

이때는 3번의 진입차수가 0이므로 큐에 3번을 추가해 준다.

 

이런 식으로 큐가 빌 때까지 반복하면 사이클이 없는 방향 그래프에서 노드 순서를 찾는

위상정렬 알고리즘을 구현할 수 있다.

 

package boj;

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

public class BOJ2252 {
    public static void main(String[] args) throws Exception {
        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());

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

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            d[e]++;
            list.get(s).add(e);
        }

        Deque<Integer> q = new ArrayDeque<>();
        for(int i = 1; i < d.length; i++){
            if(d[i] == 0) q.addLast(i);
        }
        StringBuilder sb = new StringBuilder();

        while(!q.isEmpty()){
            int num = q.pollFirst();

            sb.append(num).append(" ");
            for(int i: list.get(num)){
                d[i]--;
                if (d[i] == 0) q.addLast(i);
            }
        }

        System.out.println(sb);

    }
}