백준 2252 - 줄 세우기

2252번: 줄 세우기 (acmicpc.net)

2252번: 줄 세우기

 

오늘 포스팅 해볼 문제는 백준 2252 - 줄 세우기 문제이다.

이 문제의 경우 전형적인 위상정렬 문제인데, 그렇다면 위상정렬이란 무엇일까?

 

※ 위상정렬이란?

- 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미한다.

 

특정한 노드로 들어오는 간선의 개수를 진입차수라 한다.
1. 진입차수가 0인 노드를 큐에 담는다.

2. 큐가 비어있을 때까지 다음의 과정을 반복한다.
  1 ) 큐에 담긴 노드를 꺼내어 해당 노드에서 출발하는 모든 간선을 그래프에서 제거한다.

  2 ) 진입차수가 0인 노드를 큐에 담는다.
 
모든 원소를 방문하지 않았는데 큐가 비었다는 것은 사이클이 발생했다는 것을 의미한다. 
큐에 담기는 노드가 2개 이상인 경우, 위상 정렬된 후의 결과가 여러 개일 수 있다.

 

사실 문제를 처음볼 때는 단순히 순서대로 줄을 세우는 문제라고 생각했으나, 마지막 출력문에서 답이 여러개인 경우에는 아무거나 출력하면 된다는 것을 보고, 큐에 담기는 노드가 2개 이상인 경우를 의미한다는 것을 눈치 챌 수 있었다. 

이 문제는 사실상 위상정렬 알고리즘을 구현하는 코드와 완전히 동일하게 코드를 작성하면 된다.

 

 

※ 알고리즘

1. 그래프 배열에 값을 담아준다.

2. 진입차수가 0인 노드를 큐에 담는다.

3. 큐에 담긴 노드를 꺼내서 1개씩 줄여가면서 0이 되는 상황의 노드를 큐에 담아준다.

 

이 알고리즘을 따라서 코드를 작성하면

import sys
input = sys.stdin.readline
from collections import deque

def read_input():
    n, m = map(int, input().split())
    arr = [[] for _ in range(n+1)]
    in_Degree = [0 for _ in range(n+1)]

    for i in range(m):
        a, b = map(int, input().split())
        arr[a].append(b)
        in_Degree[b] += 1
    return n, arr, in_Degree

def sorting(n, arr, in_Degree):   
    q = deque()
    for i in range(1, n+1):
        if in_Degree[i] == 0:
            q.append(i)

    result = []
    while q:
        curr = q.popleft()
        result.append(curr)
        for i in arr[curr]:
            in_Degree[i] -= 1
            if in_Degree[i] == 0:
                q.append(i)
    return result

n, arr, in_Degree = read_input()
sorted_students = sorting(n, arr, in_Degree)
print(*sorted_students, sep=" ")

 

이렇게 코드를 모두 작성할 수 있다.