[알고리즘][Python] 백준(BOJ) 1766 문제집_파이썬

 

1766 문제집    www.acmicpc.net/problem/1766

1766번: 문제집

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 그래프 이론, 자료 구조, 우선순위 큐, 위상 정렬

 

 

 

 

 

 

 

풀이

<내용>

• 가능하면 쉬운 문제부터 풀어야 하고 문제는 난이도 순서로 출제되어 있으므로 heap을 사용해서 해결하면 된다.

 

<코드>

import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
problems = [0 for _ in range(n+1)]
graph = {}
for _ in range(m):
    a, b = map(int, input().split())
    problems[b] += 1
    if a in graph:
        graph[a].append(b)
    else:
        graph[a] = [b]
        
que = []
for i in range(1, n+1):
    if problems[i] == 0:
        heapq.heappush(que, i)
        
res = []
while que:
    i = heapq.heappop(que)
    res.append(i)
    
    if i in graph:
        for j in graph[i]:
            problems[j] -= 1
            if problems[j] == 0:
                heapq.heappush(que, j)
                
print(*res)

 

 

 

 

 

 

 

+) 비슷한 문제 해결 방법

2020/09/29 - [Algorithm/백준 알고리즘] - [알고리즘][Python] 백준(BOJ) 2252 줄 세우기_파이썬

[알고리즘][Python] 백준(BOJ) 2252 줄 세우기_파이썬