[백준] 2252번 줄 세우기 - 파이썬(Python)

문제 (링크)

 

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

2252번: 줄 세우기

 

나의 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
in_degree = [0] * (n + 1)
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    in_degree[b] += 1
    graph[a].append(b)

queue = deque()
ans = []

for i in range(1, n+1):
    if in_degree[i] == 0:
        queue.append(i)

while queue:
    current = queue.popleft()
    ans.append(current)

    for x in graph[current]:
        in_degree[x] -= 1

        if in_degree[x] == 0:
            queue.append(x)

print(*ans, end=" ")

코드 설명 및 풀이법

처음엔 학생의 최소 위치를 기록해주는 느낌으로 접근했다.

 

만약에 1, 3과 2, 3이 input으로 들어온다면, 뒤에 나온 3은 무조건 1과 2보다 뒤에 있어야함으로 3의 최소 위치인 숫자 2를 기록해준다.

 

그리고 1과 2는 3보다 앞서기만 한다면 어느 곳에 위치해도 상관 없기 때문에 결국엔 [0, 0, 2] 이런 식의 기록이 나오게 된다.

 

이걸 index와 함께 정렬해서 출력해주는 방식으로 접근했는데, 만약 (1, 3), (2, 3), (3, 4), (1, 4), (2, 4), (5, 3)과 같은 숫자가 기록된다면, 각 학생의 최소 위치는 [0, 0, 3, 3, 0]이 된다.

 

이렇게 된다면, 1, 2, 5번 학생을 배열하는 것엔 아무 문제가 없겠지만 3, 4번 학생을 배열할 때 최소 위치가 같으므로 3, 4나 4, 3 모두 가능한 배열이 되어버린다.

 

즉, 앞서 나온 3이 4보다 앞선다는 조건을 위배하는 것이다.

 

조금 더 고민해보다가, 위상정렬이라는 알고리즘을 사용해서 간단히 해결할 수 있다는 걸 알게 되었다.