[baekjoon] 백준 1766번(파이썬): 문제집

문제

1766번: 문제집

알고리즘

- bfs 탐색과 위상 정렬을 통해 문제를 수행한다.

- 선행 문제의 개수를 반복문을 통해 확인한다.

- 선행 문제 필요 없이 풀 수 있는 문제부터 힙 푸시하여 탐색한다.

- 연결된 문제를 탐색하면서 선행 문제의 개수를 -1 해준다.

- 선행 문제의 개수가 0인 문제를 힙 푸시하여 탐색한다.

- 탐색한 문제는 결과 리스트에 추가한다. 

코드

import sys
import heapq


# bfs 탐색
def bfs():

    # heap 리스트의 요소가 없을 때까지 반복
    while heap:
        # 제일 쉬운 문제를 팝한다.
        x = heapq.heappop(heap)
        res.append(x) # 문제를 풀었으므로 결과 리스트에 추가

        # 현재 문제를 풀고 풀 수 있는 문제를 확인
        for i in graph[x]:
            visited[i] -= 1 # 간선의 개수를 빼준다. 즉, 선행 문제 개수를 빼준다.

            # 다음 풀 수 있는 문제의 간선 개수가 0이면 문제를 푼다.
            # 더 이상 선행 문제가 없으면 현재 문제를 탐색한다.
            if visited[i] == 0:
                heapq.heappush(heap, i)


n, m = map(int, sys.stdin.readline().split())
heap = []
graph = [[] for _ in range(n + 1)] # 그래프
visited = [0] * (n + 1) # 각 문제의 간선 개수
res = []

# 먼저 푸는 것이 좋은 문제에 대한 정보를 입력 받는다.
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b) # 그래프로 표현
    visited[b] += 1 # 간선의 개수 체크

# 간선의 개수가 0인 문제를 힙의 푸시, 선행 문제 없이 풀 수 있는 문제를 푸시
for i in range(1, n + 1):
    if visited[i] == 0:
        heapq.heappush(heap, i)

bfs() # bfs 탐색

print(*res)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법