백준 1432 그래프수정/ python/ 위상정렬

예제 입력:
5
00001
00010
00000
00001
00100

예제 출력:
1 2 5 3 4

일반 위상정렬시 답은 (1 2 4 5 3) or (2 4 1 5 3) or (2 1 4 5 3) 등등...

문제조건 :

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

따라서, 최소힙을 사용하여 작은 것부터 뽑아줘야 한다고 생각했다.

최소힙 사용시 : 1 2 4 5 3
여기서,
N = 1, 2, 3, 4, 5에 각각의 위치를 대입해주면,
1 2 4 5 3 => 1 2 5 3 4

anw[now] ---- N++

1 2 4 5 3,  ----- N++
anw[1] = 1
anw[2] = 2
anw[4] = 3
anw[5] = 4
anw[3] = 5
-> anw = [1,2,5,3,4]

anw = [1,2,5,3,4]
정답 = [1,2,5,3,4]

이 과정에 대한 코드 :

    N = 1
    while q:
        now = heappop(q)
        anw[now] = N

        for k in graph[now]:
            degree[k] -= 1
            if degree[k] == 0:
                heappush(q, k)
        N += 1

백준의 모든 예제를 통과하지만, 답안을 제출하면 오답이다.

틀린코드 부터 보면,
위상정렬을 최소힙으로 정렬하면:

import sys
from heapq import heappop, heappush


def topology_sort():
    q = []
    for i in range(1, n + 1):
        if degree[i] == 0:
            heappush(q, i)
    N = 1
    while q:
        now = heappop(q)
        anw[now] = N

        for k in graph[now]:
            degree[k] -= 1
            if degree[k] == 0:
                heappush(q, k)
        N += 1


n = int(sys.stdin.readline())
anw = [0] * (n + 1)
degree = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]
for _ in range(1, n + 1):
    tmp = [0] + list(map(int, sys.stdin.readline().rstrip()))
    for i in range(1, n + 1):
        if tmp[i] == 1:
            graph[_].append(i)
            degree[i] += 1

topology_sort()
if anw.count(0) > 1:
    print(-1)
else:
    print(*anw[1:])

(대략적인 과정)

1. 진입차수가 0인 index를 heap = [] 에 담는다.

• heap = [1,2]

2. now = heapq.heappop(heap) & anw.append(now)

• heap = [2]

3. tmp (지금은 1)을 진입차수로 갖는 애들의 in_degree를 1 낮춰준다.
4. 만약 낮췄는데 degree 가 0이되면 -> heappush(heap, 0 이된 친구)

• heap = [2]

5. heap 이 empty 가 될때까지 반복.

오답이다

반례는 다음과 같다.

4
0011
0000
0000
0100

출력 : 1 4 2 3
정답 : 1 3 4 2

왜 최소힙으로 정렬하면 사전순으로 정렬이 안될까?

예시로 보자...

ab, ba, ac (raw data)

이것을 사전 순으로 정렬한다고 하자.
우선순위가 가장 큰 것은 첫번째 알파벳이다.
우선순위가 큰 순서대로 정렬을하면,

ab , ac, ba (1st)

다음 순서인 두 번째 알파벳을 사전순으로 정렬을 하게되면,

ba, ab, ac (2nd)

이처럼 우선순위가 큰 순서대로 정렬을 하게되면, 원하는 결과를 얻지 못한다.

만약 우선순위가 작은 것부터 (뒤에 알파벳을 사전순으로) 정렬을 한다면?

ab, ba, ac* (raw data)

ba, ab ,ac (1st)
ab, ac ,ba (2nd)

어떤 단어들을 사전순으로 정렬하기 위해서, 우선순위가 큰 순서대로 정렬을 하게되면 대부분(?) 원하는 결과물을 얻을 수는 있지만, 반례가 존재하고 원하는 결과물을 얻지 못할 수가 있다. 하지만, 우선순위가 작은 것부터 정렬을 하고 가장 마지막에 우선순위가 큰 것을 정렬을 하면 항상 옳은 결과물을 얻을 수 있다.

따라서,
진입방향을 바꿔서 입력받고, 최대 힙으로 최대값을 먼저 출력하여 맨뒤로 밀어주는 방식으로 풀면 정답이다.

정답코드:

import sys
from heapq import heappop, heappush


def topology_sort():
    q = []
    for i in range(1, n + 1):
        if degree[i] == 0:
            # heappush(q, i)
            heappush(q, -i)
    # N = 1
    N = n
    while q:
        now = -heappop(q)
        anw[now] = N

        for k in graph[now]:
            degree[k] -= 1
            if degree[k] == 0:
                heappush(q, -k)
        # N += 1
        N -= 1


n = int(sys.stdin.readline())
anw = [0] * (n + 1)
degree = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]
for _ in range(1, n + 1):
    tmp = [0] + list(map(int, sys.stdin.readline().rstrip()))
    for i in range(1, n + 1):
        if tmp[i] == 1:
            # graph[_].append(i)
            # degree[i] += 1
            graph[i].append(_)
            degree[_] += 1
topology_sort()
if anw.count(0) > 1:
    print(-1)
else:
    print(*anw[1:])
# 4
# 0011
# 0000
# 0000
# 0100

끝으로...
이 문제를 이해하는데 많은 시간을 투입했다.
sorting 과정을 직접 손으로 그려가며 해보니
이해에 많은 도움이 된 것 같다.

잘못된 내용 바로잡아 주시면 감사하겠습니다.