1766번 문제집

문제

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

접근 방식

선행되는 노드를 먼저 방문해야 하고, 문제 번호가 커지는 순으로 풀어야 한다.

예시 입력으로

> 5 3
> 4 2
> 3 1
> 1 5

가 주어진 경우,

3 -> 1 -> 5 -> 4 -> 2 순으로 풀면 조건1은 만족하겠지만, 2를 만족하지는 못한다. 2를 만족하기 위해서는 3 -> 1 -> 4 -> 2 -> 5 가 올바른 순서다.

방향성이 존재하고 항상 모든 문제를 풀 수 있다고 하므로 사이클이 존재하지는 않을 것이다. 위상 정렬 + BFS로 풀면 되는 문제다.

다만 웬만하면 숫자가 앞서는 걸 먼저 풀어야 하므로, min heap에 넣고 관리하는 것이 편하다.

코드

#문제집
import sys
input = sys.stdin.readline

from heapq import heappop, heappush

def topological_sort(n, info):
    graph = {i + 1 : {'incoming' : 0, 'dest' : []} for i in range(n)}
    for a, b in info:
        graph[a]['dest'].append(b)
        graph[b]['incoming'] += 1
    for k in graph.keys(): #목적지 sort
        graph[k]['dest'].sort()
    return graph

def solution(n, info):
    graph = topological_sort(n, info)
    heap = [] #min heap에 source 넣고 시작
    for k in graph.keys():
        if graph[k]['incoming'] == 0:
            heappush(heap, k)
    res = [] # BFS - heap 활용
    while heap:
        cur = heappop(heap)
        res.append(cur)
        for next in graph[cur]['dest']:
            graph[next]['incoming'] -= 1
            if graph[next]['incoming'] == 0:
                heappush(heap, next)
    return res

n, m = map(int, input().split())
info = []
for _ in range(m):
    info.append(map(int, input().split()))
res = solution(n, info)
for x in res:
    print(x, end = ' ')

크게 두가지 파트로 나뉜다

1. topological_sort : 위상정렬 part

단순 리스트인 순서 정보를 진입 정보, 다음 행선지 정보인 딕셔너리로 나타내려고 한다.

다음과 같은 자료구조다 :

<graph>

노드# : {
	'incoming' : 0,
    'dest' : [다음 방문 노드들]
}

incoming이 0인 노드들은 그래프의 출발점이다.

이 문제에서는 모든 번호의 수를 다 풀어야하므로, 모든 번호에 대해서 딕셔너리를 초기화 했다.

2. min heap + BFS

두번째 조건인 "문제 번호가 커지는 순으로 풀어야 한다"를 충족시키기 위해 min heap을 사용했다.

여기서 heap 변수는 "다음에 풀 수 있는 문제들의 목록"이다.

min heap에서 pop한 노드는 무조건 제일 작다는 게 보장된다.

현재 노드에서 다음 노드들에 대해 incoming 값을 체크해서 min heap에 추가하는데, 이건 다음과 같은 상황을 방지하기 위해서이다.

ex.

1 -> 3
2 -> 3

3 : {'incoming' : 2, ..}

만약 1에서 다음 노드인 3을 바로 추가한다면, 1 - 3 - 2 순으로 방문할 수 있다. 그러나 3을 풀기 위해서는 1과 2를 선행으로 풀어야 하므로, 3의 incoming이 없을 때 다음에 풀 수 있다는 게 보장된다 (= heap에 추가한다)