[백준 파이썬 1432번 그래프 수정] 생각의 전환의 전환 with 위상정렬

 

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

1432번: 그래프 수정

 

이번 문제의 핵심은 

답이 여러 개일 경우에는 사전 순으로 제일 앞서는 것을 출력한다.

 

사실 중복되는 답을 찾는 것은 위상정렬만 알면 어렵지 않다. 하지만 사전 순이 매우 큰 난관이었다.

 

핵심적인 아이디어는

1. 반대로 위에서 내려오는 방식으로 생각할 것

2. 최대 힙을 활용해 큰 인덱스부터 찾을 것

 

1번까지는 스스로 생각했는데 2번을 생각하지 못해 해결하지 못했다.

"거꾸로 생각해도 작은 것부터 찾으니까 어짜피 똑같네" 라고 판단해버렸다.

 

힙을 사용할 생각도 했는데 이번에는 1번과 합치지 못해서 실패...

1번과 2번을 동시에 생각할 수 있어야 풀 수 있었던 문제

 

from heapq import heappop, heappush


def topo():
    heap = []
    result_ls = []
    for i in range(1, N + 1):
        if check[i] == 0:
            heappush(heap, -i)

    while heap:
        now = -heappop(heap)
        result_ls.append(now)
        for nxt in graph[now]:
            check[nxt] -= 1
            if check[nxt] == 0:
                heappush(heap, -nxt)

    if len(result_ls) == N:
        num = 1
        ans_ls = [0 for _ in range(N+1)]
        for ans in reversed(result_ls):
            ans_ls[ans] = num
            num += 1
        print(*ans_ls[1:])

    else:
        print(-1)


N = int(input())
graph = [[] for _ in range(N+1)]
check = [0 for _ in range(N+1)]
for i in range(1, N+1):
    rows = '0'+input()
    for j in range(1, N+1):
        if rows[j] == '1':
            check[i] += 1
            graph[j].append(i)

topo()

 

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