[백준] 2252 줄 세우기 (Python 파이썬)

문제 설명

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

2252번: 줄 세우기

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

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

---

풀이 과정

전형적인 위상정렬 문제이다.

A번 학생이 B번 학생보다 반드시 먼저 앞에와야 하는 상황이 주어지기 때문에,

A -> B를 만족시키면서 정렬을 해야 하기 때문이다.

 

위상정렬의 과정은 다음과 같다.

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번과 4번을 먼저 줄 세우겠다는 뜻 )

큐에서 먼저 3을 꺼내 3과 연결된 간선들을 제거한다.

(3은 이미 줄을 섰으므로 3 다음에 와야 할 것들은 언제와도 무방)

 

따라서 위상정렬로 위의 방식대로 해결한 풀이는 다음과 같다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]
inDegree = [0 for _ in range(n+1)]
queue = deque()
answer = []

for i in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    inDegree[b] += 1

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

while queue:
    tmp = queue.popleft()
    answer.append(tmp)
    for i in graph[tmp]:
        inDegree[i] -= 1
        if inDegree[i] == 0:
            queue.append(i)

print(*answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !