[백준] 2252번 - 줄 세우기 / 골드 3 / 파이썬 풀이

문제 링크

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

2252번: 줄 세우기

시간 제한 : 2초

메모리 제한 : 128 MB

 

문제 요약

• N명의 학생들을 키 순서대로 줄을 세운것이다. (N은 입력으로 주어짐)
• 두 학생의 키를 비교하는 방법을 사용할건데,
  N명의 학생들을 모두 비교한 것이 아니라, 일부 학생들의 키만 비교한다.
• 키를 비교한 횟수 M (입력으로 주어짐)
• 첫째줄 다음 M개의 줄에는 키를 비교한 두 학생의 번호가 주어지는데, 
  앞에 위치한 학생이 키가 더 작아서 앞에 서야 한다는 것을 의미함.
  ex) 1 3 => 1번이 3번보다 키가 작다. => 줄 서는 순서도 '1 3' 이 되어야 한다.
  
  
• 문제 : 일부 학생들의 키만 비교하여, 전체 학생들의 키 순서대로 배치한 결과를 출력하라.
  
  
• 종료 조건
  - 첫째줄을 제외한 M 개의 줄이 입력되면 프로그램 종료. (M 번의 비교)

 

입력

예제 입력 1

3 2
1 3
2 3

예제 입력 2

4 2
4 2
3 1

 

출력

예제 출력 1

1 2 3

예제 출력 2

4 2 3 1

---

풀이

 

"위상정렬! 키가 작은 놈은 더 이상 비교할 필요가 없다고 보고 진입차수를 -1 하여 최종적으로 0이 되게끔 한다."

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())       # n 명의 학생들  /  m 번의 키 비교 횟수

inDegree = [0] * (n+1)      # 진입차수(in-degree)가 0인 학생들을 큐에 넣을 것이다.
                            # (n+1을 한 이유는, 인덱스로 인해 헷갈리지 않기 위함.)
inDegree[0] = -1            # 0번째 인덱스는 -1로 초기화하여 위상 정렬 알고리즘에 영향 받지 않도록.

direct = [[] for _ in range(n+1)]

queue = deque()

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())   # 첫째줄 다음으로 입력받는 m 개의 줄에서, 두 학생의 키 비교가 된 결과 입력 받음.
    inDegree[b] += 1        # b가 키가 더 크므로, 다른 친구와 비교가 더 되어야 하니까, 진입차수가 늘어나는 것으로 한다.
    direct[a].append(b)     # 차수 확인을 위한 리스트 direct

for i in range(1, n+1):         # 진입차수가 0인 것을 뽑아내는 과정.
    if inDegree[i] == 0:
        queue.append(i)         # 진입차수가 0인 놈은 큐에 넣어둔다.

while queue:
    q = queue.popleft()         # 제일 먼저 큐에 들어온 놈이 키가 제일 작은 놈.
    print(q, end=' ')
    for d in direct[q]:
        inDegree[d] -= 1
        if inDegree[d] == 0:
            queue.append(d)

 

참고

https://sungmin-joo.tistory.com/83

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

https://blog.naver.com/ndb796/221236874984 - 위상 정렬 개념

25. 위상 정렬(Topology Sort)