백준 2252 줄세우기 (골드 3)

백준 2252 줄세우기 (골드 3)

링크: 2252 줄세우기

---

접근 방법

• (도움) 위상 정렬로 그래프가 순환되지 않을 때, 사용 가능
• 현재 문제는 줄세우기로 순환될 수 없어 위상 정렬로 구현 가능

---

소스 코드

소스 코드: 위상 정렬 알고리즘

import sys
input = sys.stdin.readline

# 입력
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
in_graph = [0] * N
for m in range(M):
    A, B = map(int, input().split())
    graph[A-1].append((B-1, 1))
    in_graph[B-1] += 1

# 앞에 있는 수가 없을 때
queue = []
for idx, val in enumerate(in_graph):
    if val == 0:
        queue.append(idx)
        in_graph[idx] = -1

output = []
while queue:
    idx = queue.pop()
    output.append(idx+1)

    for i, val in graph[idx]:
        in_graph[i] -= 1

        if in_graph[i] == 0:
            queue.append(i)
            in_graph[i] = -1

print(*output, sep=" ")

---

코드 개선 사항(GPT 4o)

• 없음

결론

• 위상 정렬에 대해서는 처음 다뤄봐서 힌트를 보면서 했다.
• 코드 구현 자체는 쉬웠고, 최적화할 때 인접 리스트 활용을 놓치지 않아야할 것 같다.