[Python, 2252번] 줄 세우기

---

☑️ [Python, 백준/2252번] 줄 세우기

1️⃣ 문제

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

2️⃣ 접근

위상정렬.. Topology Sort... 이 개념을 공부하고 있다가 이해가 가지 않았다. 위상정렬이 DAG에서 선형적으로 보일 수 있게끔 정렬하는 알고리즘인 것은 알겠는데.. 왜 이런 알고리즘이 있어야 하나? 싶은 생각이 있어서 문제를 풀면서 어떤 상황에서 사용할 수 있을지 생각해보기로 했다.

 

그렇기 때문에 줄 세우기 문제도 위상정렬을 통해서 접근할 수 있다는 점을 알고 있는 상태에서 접근했다. 위상 정렬은 단순하게 탐색이 되었을 때, Indegree를 1씩 제거하면서 Indegree가 0인 것 부터 탐색을 돌아주면 된다.

 

지금 코드에서 안좋은 포인트는 indegree가 0인지 식별하는 코드가 2번 사용되는 것이다. 중복되는 문제가 있어서 이걸 줄이고 싶은데.... 어떻게 해결할 수 있을지 생각해봐야겠다.🥺

3️⃣ 코드

import sys
from collections import deque

def topological_sort():
    queue = deque()
    
    for i in range(1, std_num + 1):
        if indegree[i] == 0:
            queue.append(i)
    while queue:
        num = queue.popleft()
        print(num, end=" ")
        for i in graph[num]:
            indegree[i] -= 1
            if indegree[i] == 0:
                queue.append(i)

if __name__ == "__main__":
    std_num, change_num = map(int, input().split())
    
    indegree = [0] * (std_num + 1)
    
    graph = [[] for _ in range(std_num + 1)]
    for _ in range(change_num):
        a, b = map(int, input().split())
        graph[a].append(b)
        indegree[b] += 1
    
    topological_sort()