위상정렬_2252_줄세우기

이제 슬슬 그래프에 대한 모든 개념을 정복하기 위해서 위상정렬 문제를 풀이하면서 간단하게 개념을 소개할까 한다. 그래프의 종류에 대해서는 아래 필자의 블로그를 학습하고 오기를 바란다.

https://cm-me0410.tistory.com/78

그래프(Graph)의 종류

위상정렬(Topology Sort)은 사이클이 없는 방향 그래프에서 노드간의 순서를 찾는 알고리즘이다. 노드의 수를 V, 에지의 수를 E라고 했을 때, 시간 복잡도는 O(V+E)이다. 위상정렬을 문제에 적용할 때는 두 가지 조건을 명확하게 확인해야 한다. 사이클이 존재하면 노드간의 순서를 명확하게 정의할 수 없기 때문에 사이클은 반드시 없어야 하며, 항상 유일한 값으로 정렬되지 않고, 정렬 결과 경우의 수가 여러 가지일 수 있다. 

위상 정렬을 이해하기 위해서는 진입 차수를 이해한다. 그래프의 용어에 대한 정의 또한 위의 링크에 정리되어 있으므로 참고하길 바란다.

진입 차수(in-degree)는 자기 자신을 가리키는 에지의 개수이다. 즉, 방향성이 있는 그래프라고 했으니, 나를 가리키는 노드의 수를 진입차수라고 한다. 위상정렬의 원리는 아래와 같다. 이해가 조금 부족하더라도 자세한 예시는 이번에 풀이 할 문제를 설명하면서 진행할테니 일단은 보고 넘어가자. 여기서는 요점만 정리하도록 하겠다. 

1. ArrayList(인접리스트)를 사용해 그래프를 표현하는데, 각 노드가 향하는 노드를 저장하면서 표현한다. 
2. 진입차수 배열(arr)을 만들어서 값을 업데이트 한다. 예를 들어 1번 노드가 4, 5번 노드를 가리킨다고 하면 arr[4]++, arr[5]++을 한 번씩 진행해주는 것이다. 즉, 1차원 배열의 인덱스가 노드 번호인 셈이고, 나를 향하는 노드가 1개 있을 때마다 인덱스의 값을 1씩 증가시키면서 누적하는 것이다 .
3. 위상정렬 큐를 새로 만들고, 2에서 초기화 한 진입차수 배열에서 값이 0인 것을 위상 정렬 큐에 넣는다. 
4. 인접리스트에서 위상 정렬 큐에 들어간 값(노드번호)가 가리키는 노드들의 값(진입차수)을 1씩 뺀다.
5. 3~4의 과정을 모든 노드가 정렬될 때까지 반복하면 위상 정렬 큐에는 정렬된 결과가 남게 된다.

자 이제 오늘의 문제를 한 번 풀어보자.

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

2252번: 줄 세우기

 

학생들의 키를 정렬해야 하는데, 우리가 지금껏 보던 방식과는 완전히 다른 방식이다. 왜 이러는 건지,,, 흠흠 무튼 전체 학생수 N, 비교 횟수 M 그리고 비교 결과를 A, B로 주는데 이는 A > B라는 뜻이다. 여기서 중요한 조건을 하나 살펴보자면 출력에 대한 설명 가장 마지막에 "답이 여러 가지일 경우에는 아무거나 출력한다."라고 나와있다. 이는 항상 유일한 정렬 결과를 도출하지 않는 위상정렬의 원리를 반영한 것이라고 할 수 있다. 

그렇다면 문제에서 주어진 자료를 그래프적으로 해석을 해보자. 학생을 노드로 생각을 하고, 입력으로 주어진 비교 결과를 에지로 간주하여 에지리스트를 표현해보자. 예제 입력에 대한 결과를 보니 키가 가장 큰 사람부터 앞에 세우는 결과라는 것을 확인할 수 있을것이다.

그렇다면 키가 큰 사람이 작은 사람을 가리키도록 생각을 하면서 그래프로 표현해보자. 크기가 4 > 2 > 3 > 1이라고 한다면, 4 -> 2 -> 3 -> 1이라고 가정해볼 수 있을것이다. (느낌만 이해하자 실제 그래프가 이렇게 구성되지는 않는다.)

위의 가정을 기반으로 그래프를 그려보면 아래와 같다. 

필자가 정리한 그래프의 종류를 보고 왔다면, 사이클이 없고, 방향은 있으며, 비 연결 그래프이자, 컴포넌트가 2개인 그래프라고 볼 수 있다. 그렇다면 아래의 그림을 참고해서 위에서 필자가 언급한 원리를 그대로 적용하면서 진행해보자.

1. 진입차수가 0인 노드 3을 큐에 저장한다.(여기서 미리 이야기 하자면, 3을 먼저 큐에 넣느냐, 4를 먼저 넣느냐의 따라 정렬된 결과가 달라진다. 이 때문에 위상정렬은 결과가 유일하지 않다고 한 것이다.)
2. 큐에서 데이터를 poll()로 꺼내서 위상정렬 배열에 추가하고, 해당 노드가 가리키는 노드의 진입차수를 인접리스트를 사용해 접근하여 -1씩 한다. 
3. 감소했을 때, 진입차수가 0이되는 노드를 큐에 추가한다. 큐가 빌 때까지 이 과정을 반복한다. 

 

[ 전체 소스 코드 ]

위의 필자가 정리한 순서대로 소스코드의 주석을 달아두었으니 참고하기 바란다.

package Sort;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class _2252_줄세우기_위상정렬 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        //1. 인접리스트 생성 및 초기화
        List<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=N; i++) {
            list.add(new ArrayList<Integer>());
        }
        
        //2. 진입 차수 배열 생성 및 초기화 
        int inDegree[] = new int[N+1];
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            
            list.get(A).add(B);
            inDegree[B]++; //A->B이므로 B의 진입차수를 1 증가시킨다. 
        }
        
        //3. 위상 정렬 큐를 만들어서 본격적으로 정렬 시작하기 
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i=1; i<=N; i++) {
            if(inDegree[i] == 0) {
                q.add(i);
            }
        }
        
        //위상 정렬큐에 값이 없을 때까지 반복한다. 
        while(!q.isEmpty()) {
            int now = q.poll();
            sb.append(now).append(' ');
            for(int node : list.get(now)) {//4. 노드 now가 가리키는 노드들의 진입차수를 1씩 감소시킨다.
                inDegree[node]--;
                
                if(inDegree[node] == 0) {//5. 감소의 결과가 0이라면 또한 큐에 추가한다. 
                    q.add(node);
                    
                }
            }
        }
        
        System.out.println(sb);
        
    }
}