[Baekjoon] 줄 세우기(python)

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

문제 접근

위상 정렬(Topological Sorting)을 이용하는 문제이다.

 

위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행할 때 사용할 수 있는 알고리즘이다.

 

위상 정렬에 대한 자세한 설명은 풀이 과정을 통해 다루도록 한다.

---

풀이 과정

1. 위상 정렬이란?

-> 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

위상 정렬은 다음의 조건을 만족해야 적용될 수 있다.

 

1. 그래프는 방향성을 가진 그래프여야 한다.
2. 그래프에 Cycle이 없어야 한다.

위 두 조건을 한 문장으로 표현하면 위상 정렬은 DAG(Directed Acyclic Graph)인 경우에만 적용이 가능하다는 것이다.

 

2. 위상 정렬 프로세스

1. 각 정점의 진입 차수를 구한다.
2. 진입 차수가 0인 정점을 큐에 삽입한다.
3. 큐에서 원소를 꺼내고 그 원소에 연결된 간선을 모두 제거한다.
4. 간선을 제거한 후 진입 차수가 0이 된 정점을 큐에 삽입한다.
5. 1부터 다시 반복한다.

큐에서 원소를 꺼낼 때 결과값에 추가해주면 된다.

 

진입 차수가 0인 1과 6을 먼저 큐에 삽입한다.

 

큐에서 1을 꺼내어 1과 연결된 정점의 간선을 하나씩 제거하고 진입 차수가 0인 2와 3을 큐에 삽입한다.

 

큐에서 6을 꺼내어 6과 연결된 7의 간선을 제거한 후 진입 차수가 0이 되었으므로 7을 큐에 삽입한다.

 

큐에서 2를 꺼내고 2와 연결된 4의 간선을 제거한 후 진입 차수가 0이 되었으므로 4를 큐에 추가한다.

 

큐에서 3을 꺼내고 마찬가지로 5를 큐에 추가한다.

 

큐에서 7을 꺼낸다.

 

나머지 4와 5도 연결된 간선이 없으므로 하나씩 순차적으로 큐에서 꺼낸다.

---

정답 코드

"""
    백준 2252번 줄 세우기
"""

import sys
from collections import deque


def topologic_sort():
    result = []
    q = deque()

    for i in range(1, N + 1):
        if in_degree[i] == 0:
            q.append(i)

    while q:
        current = q.popleft()

        result.append(current)

        for i in graph[current]:
            in_degree[i] -= 1

            if in_degree[i] == 0:
                q.append(i)

    print(*result)


N, M = list(map(int, sys.stdin.readline().split()))
graph = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1)

for _ in range(M):
    start, end = list(map(int, sys.stdin.readline().split()))
    graph[start].append(end)
    in_degree[end] += 1

topologic_sort()