BOJ) 줄 세우기 (2252 번)

줄 세우기

2252번: 줄 세우기

 

오랜만에 포스팅을 하게 된 이유는 위상 정렬에 대한 정리를 하기 위해서이다.

 

위키에 따르면 

 

위상 정렬(topological sorting)은 방향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.
가장 대표적인 예로 대학의 선수과목(prerequisite) 구조를 들 수 있다.
만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다.
선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다.
정렬의 순서는 방향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 
위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다.
즉, 그래프가 비순환 방향 그래프(directed acyclic graph)여야 한다.

 

위상 정렬의 조건을 요약하면,

1. 방향 그래프에서 선후 관계가 정의되어있고

2.사이클이 없어야 한다.

 

위상 정렬은 위의 조건에 따라 선행해야하는 그래프의 꼭지점을 나열할 때 이용한다.

 

그렇다면 과정은 어떻게 될까??

 

> 위상정렬의 수행과정

1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음.
2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제
3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.

 

가리키는 엣지가 없는 특정 꼭지점을 찾는다. ~> 해당 꼭지점을 출력하고, 이 꼭지점에서 출발하는 엣지를 삭제한다. ~> 엣지를 삭제하고 출력하지 않은 꼭지점이 있으면 다시 처음으로 돌아가서 꼭지점을 찾는다.

 

이 정도로 요약할 수 있겠다.

 

사실, 이에 대한 이해가 처음에 되지 않아서 다른 분의 블로그를 보면서 위상 정렬에 대해 이해했다.

위의 문제 뿐만 아니라, 위상 정렬을 이용한 여러 문제를 다루고 있으니 여기에서 학습하는 것을 추천한다.

 

로직

1. 자신에게 연결된 edge의 수를 저장하는 edgeArr와 꼭지점이 연결되는 것을 표현할 graph를 선언하고 저장한다.

2. 위의 수행과정을 진행할 연결 리스트 (LinkedList)를 선언한다.

3. edgeArr를 돌면서, 자신을 가리키는 엣지가 없는 꼭지점을 찾아 연결리스트에 입력한다.

4. 연결리스트를 돌면서, 해당 꼭지점에서 이어지는 엣지를 삭제한다.

  4-1. 엣지 삭제 이후, 연결된 꼭지점의 엣지가 0이면 연결리스트에 추가한다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        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[] edgeArr = new int[n+1];

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

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            graph.get(left).add(right);
            edgeArr[right]++;
        }

        br.close();
        solution(n, graph, edgeArr);
    }

    private static void solution(int n, ArrayList<ArrayList<Integer>> graph, int[] edgeArr) {
        LinkedList<Integer> orderList = new LinkedList<>();
        final int zero =0;
        StringBuilder sb = new StringBuilder();
        final String space = " ";

        for(int i=1; i<=n; i++) {
            if(edgeArr[i] ==zero) {
                orderList.add(i);
            }
        }

        while(!orderList.isEmpty()) {
            int vertex = orderList.poll();
            sb.append(vertex).append(space);
            ArrayList<Integer> edgeList = graph.get(vertex);

            for(int nextVertex : edgeList) {
                if(--edgeArr[nextVertex] ==0) {
                    orderList.offer(nextVertex);
                }
            }
        }
        System.out.println(sb.toString());
    }
}