줄 세우기 ( 2252 번 )

2252번: 줄 세우기

 

🧠 알고리즘

- 루트인 노드를 큐에 넣고 시작!!
- 큐에서 하나씩 꺼내며 answer에 줄 세우기
- 해당 노드 자식 노드의 부모 카운트를 하나씩 줄이며, 부모가 더 이상 존재하지 않을시 큐에 추가
- 최종 결과 출력..

 

🧾 코드

from collections import deque
import sys

def _mk(num1, num2):
    a1, a2 = {}, {}
    for i in range(1, num1 + 1):
        a1[i], a2[i] = [], 0

    for _ in range(num2):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        a1[a].append(b)
        a2[b] += 1
    
    return a1, a2

def _main(ch_dict, pt_dict):
    answer = []
    queue = deque()
    for k, v in pt_dict.items():
        if v == 0: # 부모가 없는 경우
            queue.append(k)

    while queue:
        now_q = queue.popleft()
        answer.append(now_q) # 줄 세우기
        
        for ch in ch_dict[now_q]:
            pt_dict[ch] -= 1
            if pt_dict[ch] == 0: # 더이상 부모가 없는 경우
                queue.append(ch)
    
    return ' '.join(map(str, answer))


n, m = map(int, sys.stdin.readline().rstrip().split())
ch, pt = _mk(n, m)
print(_main(ch, pt))

 

⏱️ 시간 복잡도

_mk() : 자식, 부모 메타정보 만드는 함수 ( 선형 시간 복잡도 )
_main() : 줄 세우는 함수, 간선 한번 씩 스캔 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )