파이썬 백준 1432 그래프 수정

import sys input = sys.stdin.readline import heapq n = int(input()) child = [0 for i in range(n + 1)] V = [[] for i in range(n + 1)] for i in range(1, n + 1) :     l = list(input())     for j in range(1, n + 1) :         if l[j-1] == '1' :             V[j].append(i)             child[i] = child[i] + 1 child[0] = None if 0 not in child :     print(-1)     exit(0) heap = [] for i in range(1, n + 1) :     if child[i] == 0 :         heapq.heappush(heap, -i) ans = [0 for i in range(n + 1)] order = n while heap :     i = -heapq.heappop(heap)     ans[i] = order     order = order - 1     for j in V[i] :         child[j] = child[j] - 1         if child[j] == 0 :             heapq.heappush(heap, -j) for i in range(1, n + 1) :     print(ans[i], end = ' ')

아직 부모가 있는 점에 새 order를 부여하면, 나중에 그 점의 부모에 order를 부여할 때 모순이 일어난다. 즉, 항상 부모가 없는 점에 대해서만 새 order를 부여해야 모순이 생기지 않는다.

부모의 수를 세는 리스트를 만들어 큐에서 부모가 0인 점에 새 order를 부여한다. 그리고 그 자식의 부모수를 -1하여 0이라면 큐에 넣는다.

이때 우선순위 큐를 이용하여 항상 작은 수가 먼저 고려되도록 하면 사전순 최우선의 결과를 낼 수 있다.

이를 반복하여 모든 수에 대해 새 order를 부여하면 된다.

근데 오답이 떠서 찾아보니 모든걸 다 거꾸로 해야한다고 한다 ㅋㅋ

부모 대신 자식의 갯수를 세고, 연결도 거꾸로 꽂고, 자식이 0인 점들을 큐에 넣어야 한다. 역순으로 정렬하려면 최대 힙을 써야하니 힙에도 음수로 넣어야 한다.

 

생각해보면 "새 순열의 1,2,3,4...번이 원래 순열의 몇이었는지"를 출력하는 것이 아니라, "원래 순열의 1,2,3,4...가 새 순열에선 몇번인지"를 출력해야 하기 때문에 일어나는 차이이다. 즉 ans[order] = i가 아니라ans[i] =order이기 때문이다.

정순(=사전순)으로 큐에 넣은 i에 대해 앞부터 고려한다고 해도 그 결과가 사전순이라는 보장은 없다.

 

사전순으로 스트링을 정렬하려면 첫글자부터 정렬 후 뒷자리를 정렬하는 것이 아니라 뒷자리부터 정렬하며 마지막으로 첫글자를 정렬해야 하는 것처럼, 뒤에서부터 채워가며 사전순을 거스를 경우를 없애야 마지막으로 첫째자리까지 왔을때 사전순에 해당하는 결과를 얻을 수 있다.