[Baekjoon] 2252번 : 줄 세우기 (Python, 위상 정렬)

[Baekjoon] 2252번 : 줄 세우기 (Python, 위상 정렬)

 

목차

 

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

2252번: 줄 세우기

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Python

 

방법 1 - 메모리 37616KB / 시간 252ms / 코드 길이 647B

 

N명의 학생이 존재한다.

그리고 N명 중 2명의 학생만이 키에 대한 비교를 한다.

그리고 비교 A, B 학생에 대하여 먼저 주어진 A가 반드시 B보다 먼저 선행되어야 한다.

 

위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용한다.

위 문제에서 언급한 A & B 학생의 순서가 정해지는 부분에서 위상 정렬을 떠올려야 한다.

 

다만 본 문제의 차별점은 M번의 비교가 모든 학생에 대한 비교가 아니기 때문에 복수의 정답이 나올 수 있다는 점을 유의해야한다.

 

위상 정렬은 graph와 indegree 진입 차수 개념이 필요하다.

graph에는 선행되어야 하는 번호에 뒤 따라야하는 값을 저장한다.

indegree에는 후차적인 번호에 값을 1개씩 추가해야한다는 점이다.

 

가령 예를 들어 본 문제 예제 1번째를 살펴보면 N=3명 이고 M=2번의 비교가 있다.

M1 : 1 3

1번 학생이 3번 학생보다 선행되어야 한다.

M2 : 2 3

2번 학생이 3번 학생보다 선행되어야 한다.

 

여기서 graph와 indegree는 다음과 같다. (여기서 0은 생략 가능하나 순서를 맞추기 위해 넣는다.)

graph = [[], [3], [3], []]

indegree = [0, 0, 0, 2]

 

이제 여기서 queue를 활용하여 indegree가 0인 index부터 시작해서 차례로 선행되어야 하는 학생을 뽑아낸다.

이후는 자연스러운 queue 처리이다. 

 

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

n, m = map(int, input().split())

graph = [[] for i in range(n+1)]
indegree = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

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

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

    while q:
        now = q.popleft()
        result.append(now)

        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=' ')

topology_sort()