줄 세우기

간단한 위상정렬 연습문제이다.

M개의 줄에 주어진 학생들의 키를 비교해놓은 정보를 토대로 줄을 세우면 된다.

  • check 리스트에는 본인 앞에 서야할 학생이 현재 몇명 남아있는지를 저장한다.
  • bridge에는 본인보다 뒤에 서야하는 학생들의 정보를 저장한다.
  • point (heapq)를 활용해 차례로 학생들을 줄세운다.

point에서 학생 한 명을 추출해 줄을 세운다.

bridge(dictionary)를 활용해 해당 학생 뒤에 서있어야 하는 학생들의 정보를 받는다. 이 학생들의 check정보를 1씩 감소시켜주고, check가 0이 된 경우 해당 학생 앞에 서있어야 할 친구들은 모두 이미 줄을 섰다는 의미임으로 point에 추가해준다.

CODE

import heapq
import sys
read = sys.stdin.readline

n, m = map(int, read().split())
#본인 앞에 현재 몇 명이 남아있는지 check!
check = list(0 for _ in range(n+1))
#본인보다 뒤에있는 학생의 정보 저장
bridge = dict()
for _ in range(m):
    a, b = map(int, read().split())
    #b앞에 a가 반드시 서있어야 함으로 check[b]에 1 추가
    check[b] += 1
    if a in bridge:
        bridge[a].append(b)
    else:
        bridge[a] = [b]
#본인 차례가 온 학생들을 저장
point = []
for i in range(1, n+1):
    #check[i]가 0이면 i학생 앞에 서야할 사람이 없다는 뜻임으로, point에 추가
    if check[i] == 0:
        point.append(i)
#답이 여러가지인 경우에 아무거나 출력해도 됨으로 heapq를 사용했다.
heapq.heapify(point)
while point:
    a = heapq.heappop(point)
    print(a, end=' ')
    if a in bridge:
        for x in bridge[a]:
            check[x] -= 1
            if check[x] == 0:
                heapq.heappush(point, x)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]