1766 문제집

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

1766번: 문제집

 

참고한 사이트

https://freedeveloper.tistory.com/390

[이것이 코딩 테스트다 with Python] 36강 위상 정렬

 

내 풀이(너무 모르겠어서 찾아봄)

import heapq

n, m = map(int, input().split())

graph = [[] for i in range(n+1)]
indegree = [0 for i in range(n+1)]
queue = []
answer = []

for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    indegree[y] += 1

for i in range(1, n+1):
    if indegree[i] == 0:
        heapq.heappush(queue, i)
        
while(queue):
    t = heapq.heappop(queue)
    answer.append(t)
    for i in graph[t]:
        indegree[i] -= 1
        if indegree[i] == 0:
            heapq.heappush(queue, i)

for i in answer:
    print(i, end = " ")

이 문제는 위상 정렬을 사용했다. 위상 정렬은 선수 과정이 있는 경우에 적용할 수 있다. 하지만 만약 사이클이 돌아가면 위상 정렬 알고리즘을 적용할 수 없다.

graph는 문제의 방향을 나타내는 것, indegree는 들어오는 간선의 수, queue 큐를 활용, answer 최종 답을 저장

첫번째 for문: 그래프 방향을 입력 받고 저장

두번째 for문: 간선의 수가 0인 문제를 queue에 저장

while문: queue가 빌 때 까지 수행한다. 작은 번호부터 먼저 풀어야하는 것이라 heappop로 queue에서 작은 번호를 answer에 넣어준다. 그리고 넣은 번호에 연결된 번호의 들어오는 간선 수를 -1 해준다. 이때 만약 그 번호의 간선 수가 0이되면 queue에 넣어주고 반복한다.