[백준] 2252번 줄 세우기 파이썬 해설

 

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

 

입사 후 교육을 받는 기간이라 주말에 간간히 한 두 문제 정도 풀 수 있다..ㅜ

심지어 회사와 관련된 내용과 지식은 보안상 조심해야 한다고 하기 때문에 퇴사 전 까지는 알고리즘 문제 풀이 정도나 올릴 것 같다.

 

오늘은 동기들을 통해 추천받은 "위상 정렬" 알고리즘 문제를 풀어봤다. 정답률도 높고, 정답의 범위도 넓기 때문에 푸는데 조금 수월했던 것 같다.

 

풀이

---

위상정렬의 개념에 대해서 공부하기 좋은 기본 문제라고 생각한다. 

a, b를 입력받을 때 a가 b를 참조한다고 생각하고, 참조 횟수가 0인 정점부터 위상 정렬을 수행하면 쉽게 문제를 풀 수 있다. 다만 참조 횟수가 0인 정점에 대해 정렬을 수행하고 나서 해당 정점이 참조하던 또 다른 정점에 대해 참조 횟수를 감소시켜주는 작업을 꼭 수행해야 한다는 것을 주의하자! (실제 코드에 주석 부분)

 

- 정답 코드

 

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

n, m = map(int, input().split())
arr = []
inDegree = [ 0 for i in range(32001)]
graph = [[] for i in range(32001)]
queue = deque()

for i in range(m):
    a, b = map(int, input().split())
    arr.append([a, b])

for a, b in arr:
    inDegree[b] += 1
    graph[a].append(b)

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

while queue:
    student = queue.popleft()
    #indegree가 0인 정점을 제거하고, 해당 정점이 참조하고있던 점들의 indegree를 감소시킨다.
    for j in graph[student]:
        inDegree[j] -= 1
        if inDegree[j] == 0:
            queue.append(j)
    print(student, end = ' ')

 

 

결과

---

한 번의 시도만에 풀었지만, 맞은 사람 보기에서 첫 페이지에 올라가지 않아서 좀 아쉽다..

매 주말마다 한 두 문제씩이라도 풀면서 프로그래밍에 대한 '감'을 꼭 유지하자!