[백준 2024/09/23] 2252번 줄 세우기

1. 문제

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

 

2. 접근 방법

위상 정렬을 사용하도록 하는 문제였다.

키의 순서를 adj에 정렬해 주고, inD라는 함수에 몇개의 진입 차수를 필요로 하는지 표현해 주었다.

 

3. 코드

from collections import deque


def topological():
    queue = deque()
    result = []
    for i in range(1, num+1, 1):
        if inD[i] == 0:
            queue.append(i)

    for _ in range(num):
        if not queue:
            return -1

        q = queue.popleft()
        result.append(q)
        for i in adj[q]:
            inD[i] -= 1
            if inD[i] == 0:
                queue.append(i)

    return " ".join(map(str, result))


if __name__ == "__main__":
    num, compare_cnt = map(int, input().split())
    adj = [[] for i in range(num+1)]
    inD = [0] * (num+1)

    for _ in range(compare_cnt):
        f, l = map(int, input().split())
        adj[f].append(l)
        inD[l] += 1

    print(topological())