[Python] 백준 1432번 그래프 수정

이번에 풀 문제는 그래프 수정 문제이다. 위상 정렬을 활용하는 문제인데, 일단 문제를 보고 가자.

- N개의 정점으로 구성된 그래프가 입력으로 주어진다. 이때 노드의 번호는 1보다 크거나 같고 N보다 작거나 같다.
- 만약 노드 U에서 노드 V로 연결되는 간선이 존재한다면, 노드 V의 번호는 노드 U의 번호보다 커야 한다.
- 위의 조건을 만족하도록 노드의 번호를 바꾸고, 원래의 1번 노드부터 N번 노드까지 각각 바뀐 노드의 번호를 출력해야 한다. 

위의 말만 봐서는 문제에서 원하는 것이 무엇인지 정확히 감이 오지 않을 수 있다. 다음 입력값을 그림으로 나타내서 이해해 보자!

n = 5
node1 : 00110
node2 : 00001
node3 : 00000
node4 : 01000
node5 : 00000

 

문제 조건을 만족하기 위해서 간선의 시작 부분의 노드가 도착 부분의 노드보다 번호가 작아야 한다.

$$\text{(시작 노드의 번호) < (도착 노드의 번호)}$$

현재 위의 조건을 만족하지 못하는 간선은 다음과 같다.

$$\text {4 -> 2}$$

노드의 번호를 문제의 조건에 맞게 바꾸면 위의 그림과 같다. 위의 그림을 잘 살펴보면, 원래 그래프에서 위상 정렬을 진행한 결과를 바탕으로 번호를 부여한 것을 알 수 있다.

다만 이 문제에서는 위상 정렬의 결과를 순서대로 작은 번호부터 부여를 하게 되면 정답과 다른 결과가 나올 수 있다. 따라서 풀이에서는 위상 정렬의 마지막 결과부터 큰 숫자를 부여하는 방식으로 진행한다! 즉 기존의 위상 정렬과 반대로 생각하는 것이다. 기존의 위상 정렬에서 in-degree를 기준으로 연산을 진행했지만, 이 문제에서는 out-degree를 기준으로 연산을 진행한다. 

 

과정에 맞게 하나하나 그림과 함께 살펴보자!

 

먼저 out-degree가 0인 5번 노드와 3번 노드를 큐에 추가한다. 큐에서 원소를 꺼낼 때마다 해당 노드에 현재까지 부여한 번호를 제외한 나머지에서 가장 큰 번호를 부여하는데, 이를 큰 노드에 큰 값을 부여하기 위해서 최대힙을 사용한다. 따라서 5번 노드에서 시작하게 되고, 5번 노드와 연결된 2번 노드의 out-degree 값을 1만큼 감소시킨다. 이후 2번 노드의 out-degree가 0이 되었으므로 큐에 추가해 준다.

 

 

 

다음으로 3번 노드를 큐에서 꺼내 검사한다. 두 번째로 꺼낸 원소이므로 change에 4를 입력해 주고, 1번 노드의 out-degree를 감소시킨다. 

 

다음으로 2번 노드를 꺼낸다. 위의 과정과 마찬가지로 4번 노드의 out-degree를 1 감소시키고, 이제 0이 되었으므로 큐에 넣어준다. 

 

이제 4번 노드를 꺼내 2번을 부여하고, 1번의 out-degree를 감소시켜 큐에 넣어준다. 

마지막으로 1번 노드에 번호 1을 부여하면 모두 끝나게 된다! 

 

위의 과정을 코드로 구현해 보면 아래와 같다. 

import sys
import heapq
input = sys.stdin.readline

n = int(input())

graph = [[] for _ in range(n+1)]
tmp = []

for _ in range(n):
    tmp.append(input().rstrip())
    
outdegree = [0] * (n+1)
change = [0] * (n+1)

h = []

for i in range(n):
    for j in range(n):
        if tmp[i][j] == '1':
            graph[j+1].append(i+1)
            outdegree[i+1] += 1
    if outdegree[i+1] == 0:
        heapq.heappush(h, -(i+1))

num = n
while h:
    now = -heapq.heappop(h)
    change[now] = num
    num -= 1
    for next_node in graph[now]:
        outdegree[next_node] -= 1
        if outdegree[next_node] == 0:
            heapq.heappush(h, -next_node)

print(*change[1:]) if not 0 in change[1:] else print(-1)