[백준] 2252번 - 줄 세우기

 

2252번: 줄 세우기

 

 

 

 

 

문제

 

N명의 학생 중 두 학생의 키를 M번 비교한 데이터가 주어질 때, 키 순서를 유추하여 줄을 세우시오. 답이 여러가지인 경우에는 아무거나 출력해도 무방함.

 

 

 

 

 

조건

 

1 <= N <= 32,000

1 <= M <= 100,000

시간 제한 2초

 

 

 

 

 

풀이 방향

 

각 학생들을 정점,  두 학생의 키를 비교한 M개의 데이터를 두 정점간의 방향이 있는 간선이라고 생각하면 해당 문제는 비순환 방향 그래프(DAG)로 치환하여 해결할 수 있다. DAG 자료구조에서 일련의 기준에 따라 정점들의 순서를 도출하고 싶을 때 사용할 수 있는 알고리즘은 위상정렬(Topology Sort)이다. 따라서 위상정렬을 사용하여 문제를 해결하면 된다.

 

위상정렬 개념

[알고리즘] 위상 정렬

 

 

 

위상 정렬을 구현하는 방법은 다음과 같다. 주어지는 모든 간선에 대하여 인접한 두 정점 중 꼬리 방향에 가까운 정점의 차수(degree)를 1만큼 증가시킨다. 그렇게 되면 머리 방향(키가 가장 큰) 에서 멀어질 수록 degree가 증가한다. 

 

for (int i = 0; i < M; i++) {
    input = br.readLine().split(" ");
    int u = Integer.parseInt(input[0]);
    int v = Integer.parseInt(input[1]);
    
    // 입력으로 주어지는 간선에 대한 정보를 List<Integer>[] link 에 담는다. u는 v보다 키가 크다는 의미
    link[u].add(v);
    // 키가 더 작은 (꼬리방향에 가까운) 정점의 차수를 1만큼 증가시킨다.
    degree[v]++;
}

 

 

 

그 다음 Queue<Integer> 객체를 생성하여 더 이상 키를 비교할 학생이 없는 경우 큐와 출력 객체에 해당 학생을 담는다. degree == 0 인 정점은 주어진 데이터만 고려했을 때 해당 학생보다 키가 큰 학생이 존재하지 않다는 것을 의미한다. 따라서 큐에 담기는 시점을 degree == 0으로 한다. 마찬가지로 키 순서대로 출력해야 하므로 마찬가지로 degree == 0이 되는 순서에 따라 출력 객체에 담는다. 

문제 조건에서 모든 학생의 키를 비교한 것은 아니며 답이 여러가지인 경우에는 아무거나 출력하라고 하였으므로 키의 대소 비교를 할 수 없는 학생들에 대해서는 순서를 신경쓰지 않아도 된다. 

 

Queue<Integer> que = new LinkedList<>();
StringBuilder sb = new StringBuilder();

for (int i = 1; i <= N; i++) {
    if (degree[i] == 0) {
        que.offer(i);
        sb.append(i + " ");
    }
}

 

 

 

그리고 que가 빌 때까지 다음 과정을 반복한다.

 

1. que에서 정점 하나(n)를 꺼낸다. 

2. n보다 작다고 알고 있는 학생들(link[n])에 대하여 degree를 1만큼 낮추고, 만약 degree == 0 이라면 해당 학생보다 큰 학생은 더 이상 없으므로(혹은 알 수 없으므로) 출력 객체와 큐에 해당 정점을 담는다.

 

위 과정을 보면 키가 큰 학생과 키가 작은 학생간에 키를 비교하는 경우 degree가 1만큼 작아진다. 따라서 degree가 0 보다 크다는 것은 해당 학생보다 적어도 1명 이상 키가 크면서 아직 대소비교를 하지 않은 학생이 존재하는 것이므로 모든 학생에 대한 degree가 0이 되지 않는 이상 while 반복문이 시작되는 시점에는 아직 키를 비교해야 되는 학생이 존재한다. 

 

경우에 따라서는 더 이상 방문할 필요가 없는 정점에 대한 방문처리를 할 수도 있지만 이번 문제에서는 이런 과정 없이도 해결이 가능하다. 

 

 

 

 

 

 

 

 

 

 

 

전체 코드

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

public class Main {
    public static void main (String[] args) throws IOException {
        new Main().solution();
    }
    
    
    int N, M, degree[];
    List<Integer>[] link;
    
    private void solution () throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = {};
        
        input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        
        degree = new int[N+1];
        link = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) link[i] = new ArrayList<>();
        
        
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            link[u].add(v);
            degree[v]++;
        }
        
        System.out.println(topology());
        
        br.close();
    }
    
    
    private String topology () {
        
        Queue<Integer> que = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        
        for (int i = 1; i <= N; i++) {
            if (degree[i] == 0) {
                que.offer(i);
                sb.append(i + " ");
            }
        }
        
        while (!que.isEmpty()) {
            
            int n = que.poll();
            
            for (int p : link[n]) {
                if (--degree[p] == 0) {
                    que.offer(p);
                    sb.append(p + " ");
                }
            }
        }
        
        return String.valueOf(sb);
    }
}