[백준 2252번] 파이썬 - 줄 세우기

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

2252번: 줄 세우기

 

 

# 조건

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

 

입력

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

 

출력

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

 

# 접근 방법

• 위상 정렬을 이용해주면 된다.
• A 학생이 B학생 앞에 서야 되므로 A와 B의 연결 표시를 남겨준다.
• 또한, B에 언급 되는 사람들의 차수를 +1 씩 해주면 된다.
• 진입차수가 0인 정점을 큐에 삽입해주고 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두 제거
• 차수가 0인 사람부터 줄을 세우며 자신보다 뒤에 있어야 되는 사람의 차수를 -1 씩 해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
N, M = map(int, input().split())  
  
student = [[] for _ in range(N+1)]  
degree = [0] * (N+1)  
que = deque()  
answer = []  
  
for _ in range(M):  
    a, b = map(int, input().split())  
    student[a].append(b)  
    degree[b] += 1  
  
  
for i in range(1, N+1):  
    if degree[i] == 0:  
        que.append(i)  
  
while que:  
    curNum = que.popleft()  
    answer.append(curNum)  
    for j in student[curNum]:  
        degree[j] -= 1  
        if degree[j] <= 0:  
            que.append(j)  
  
print(*answer)