[BOJ/Python] 2252번 문제풀이

문제 설명

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

---

풀이 과정

(으악 알고리즘 문제는 너무 어렵다...)

해당 문제는 '위상 정렬'을 활용한 알고리즘 문제라고 한다. 이 문제에 대한 풀이에 앞서 위상 정렬 알고리즘에 대해 알아보자

 

위상 정렬

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다.

위상 정렬의 특징)

• 위상 정렬은 DAG에 대해서만 수행할 수 있다.
  • DAG(Direct Acyclic Graph) : 순환하지 않는 방향 그래프
• 위상 정렬에서는 여러가지 답이 존재할 수 있다. (한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답이 존재한다.)
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
• 스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다.

 

큐를 이용하는 위상 정렬 알고리즘의 동작 과정)

1. 진입 차수가 0인 모든 노드를 큐에 넣는다
2. 큐가 빌 때까지 다음의 과정을 반복한다
   
   • 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   • 새롭게 진입 차수가 0아 된 노드를 큐에 넣는다.

[참고자료] https://freedeveloper.tistory.com/390

 

 

위상 정렬을 사용하여 이 문제를 푸는 방법은 다음과 같다.

 

1. 진입 차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거
3. 제거한 후에 진입 차수가 0인 정점을 큐에 삽입
4. 이후 2~3의 과정을 반복

이때, 학생들은 4명이 있고, 다음과 같은 조건이 주어졌다고 가정해보자

• 4 -> 2
• 3 -> 1

4번은 반드시 2번 앞에 와야 하므로 4 -> 2로의 간선이 존재하므로 2번의 진입차수는 1이 되며 3번은 반드시 1번 앞에 와야 하므로 3 -> 1로의 간선이 존재하므로 1번의 진입차수는 1이 된다.

 

먼저 진입 차수가 0인 3번과 4번을 큐에 넣은 다음 큐에서 먼저 3을 꺼내 3과 연결된 간선들을 제거한다. 따라서 위상 정렬을 해당 과정에 따라 코드를 짜면 아래와 같다.

 

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

#입력을 받으면서 인접 리스트를 만든다.
N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]

#앞에 몇명이 있는지 front 리스트에 기록한다.
front = [0] * (N+1)

for _ in range(M):
    a, b = map(int, input().split())
    arr[a].append(b)
    front[b] += 1

#q에 앞에 있어야 할 사람이 0인 사람들을 append하고, q가 빌 때까지 반복한다.
def answer():
    result = []
    q = deque()
    for k in range(1, len(front)):
        if front[k] == 0:
            q.append(k)
    while q:
        now = q.popleft()
        result.append(now)
        for nnow in arr[now]:
            front[nnow] -= 1
            if front[nnow] == 0:
                q.append(nnow)
    print(*result)


answer()