[알고리즘] 백준 1766 문제집 (위상정렬)

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

1부터 N까지의 문제가 있고, 각 문제의 선행 문제를 입력받은 뒤 문제에서 주어지는 조건에 맞추어 정렬된 문제 풀이 순서 결과를 출력하는 문제였다.

사실 이 문제가 위상정렬이라는 개념을 요한다는것도 모른채로 문제 풀이에 들어갔다. 내가 시도한 방법은 다음과 같다.

예를 들어 입력이 다음과 같이 주어졌을 때

4 2
4 2
3 1

4번 문제는 2번 문제보다 선행되어야하고 3번 문제는 1번 문제보다 선행되어야 한다.

따라서 각 문제의 번호와 중요도를 함께 리스트 또는 튜플로 담아서 중요도를 첫번째 정렬 기준으로 문제 번호를 두번째 정렬 기준으로하여 이를 pop한 결과를 정답으로 제출하였다.

아래가 내가 위상정렬을 모른채로 시도한 방법이다.

import heapq
import sys

N, M = map(int, sys.stdin.readline().split())

numbers = []
for i in range(1, N+1):
    numbers.append([i, i])

priority_queue = []

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    B_weight = numbers[B-1][0]
    if numbers[A-1][0] > numbers[B-1][0]:
        numbers[A-1][0] = B_weight - 1

print(numbers)
for i in range(N):
    heapq.heappush(priority_queue, numbers[i])

for _ in range(N):
    print(heapq.heappop(priority_queue)[1], end=' ')

입력에 따라 선행 문제의 중요도를 변경시키기 위해 가중치를 주었다. 각 문제의 중요도는 기본적으로 1, 2, 3, 4번의 경우 1번문제는 1점, 2번 문제는 2점 식으로 중요도를 가지게 하였다. (최소힙을 사용할 것이므로, 점수가 낮을수록 우선순위가 높은 문제)

그리고 입력으로 4 2가 들어왔다면 2번보다 4번의 중요도를 높여주어야 하므로, 본래 4번의 중요도였던 4를 2번의 중요도인 2로 바꾸어주고 이 값에 1을 빼주었다. 마찬가지로 3 1의 경우에도, 본래 3번의 중요도인 3을 1번의 중요도인 1로 바꾸고 1을 빼주었다.

이 과정을 거치고 나면 다음과 같이 리스트에 추가된다.
[ [1, 1], [2, 2], [0, 3], [1, 4] ] 각 리스트의 0번 요소가 중요도이고, 1번 요소가 문제의 번호이다. 이를 힙에 넣어 정렬해주면,
[ [0, 3], [1, 1], [1, 4], [2, 2] ] 가 되고 각 리스트의 1번 요소를 출력하면 3 1 4 2로 예제 입력의 결과가 나오게된다.

질문 게시판에 있는 많은 반례값들도 통과하였으나, 5번이 2번의 선행 작업으로 수행되기로 입력된 상태에서 2번이 1번의 선행작업으로 입력 받은 상태일 때, 5번이 아닌 2번이 먼저 실행되는 반례를 잡지 못해 풀이를 찾아보게 되었다.

정답 코드

아래가 위상 정렬을 이용하여 풀이한 정답 코드이다. 위상 정렬을 하기 위해서는 각 정점들의 진입차수를 먼저 리스트로 초기화를 시켜주어야한다.

그리고 각 정점에 연결된 다른 정점들을 numbers라는 2차원 리스트에 넣어서 다음 탐색의 위치로 삼을 수 있도록 관리한다.

진입 차수가 0인 정점을 큐에 넣고, 큐에서 빼기를 반복한다. 이 때 큐에서 pop된 결과들이 위상 정렬된 결과이다.

import heapq
import sys

N, M = map(int, sys.stdin.readline().split())
numbers = [[] for i in range(N+1)]
in_degree = [0] * (N+1)

priority_queue = []
results = []

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    numbers[A].append(B) # 선행 작업과 연결된 정점들 리스트로 관리
    in_degree[B] += 1 # 진입 차수 초기화

# 진입 차수가 0인 정점들을 큐에 넣는다.
for i in range(1, N+1):
    if in_degree[i] == 0:
        heapq.heappush(priority_queue, i)

while priority_queue:
	# 큐에 들어가 있는 정점을 pop하고, 이와 연결되어있는 정점들의 간선들을 모두 끊어준다(진입 차수를 줄여준다)
    temp = heapq.heappop(priority_queue)
    results.append(temp)
    for i in numbers[temp]:
        in_degree[i] -= 1
        # 진입 차수가 0이 된 정점들을 다시 큐에 넣는다. 이 과정을 반복한다.
        if in_degree[i] == 0:
            heapq.heappush(priority_queue, i)

print(*results)