[PY] <!> 1432 : 그래프 수정

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

문제 독해력부터 안된 김에 그냥 블로그부터 보았다.
핵심은 indegree 를 쫓는 형식의 위상 정렬을 반대로 outdegree로 구현하고, 또 제시하는 의도에 맞게 데이터 출력을 해야한다.

이 문제가 원하는게 뭔지부터 알기가 실패했기 때문에 이건 반드시 다시 풀어야한다. outdegree를 사용해야 답이 보장되는 이유도 알아야겠고.

https://codable.tistory.com/13

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

import sys, heapq
input = sys.stdin.readline

nodeCnt = int(input())

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

for _ in range(nodeCnt):
    tmp.append(input().rstrip())

outdegree = [0] * (nodeCnt + 1)
change = [0] * (nodeCnt + 1)

heap = []

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

num = nodeCnt
while heap:
    now = -heapq.heappop(heap)
    change[now] = num
    num -= 1

    for next_node in graph[now]:
        outdegree[next_node] -= 1
        if outdegree[next_node] == 0:
            heapq.heappush(heap, -next_node)

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