백준 1432번 python 풀이 - 그래프 수정

문제 링크

1432번

해결책

import sys

N = int(sys.stdin.readline().rstrip())

path = [[] for i in range(N + 1)]
indegree = [0 for i in range(N + 1)]

for i in range(1,N+1):
    str_in = sys.stdin.readline().rstrip()
    for idx in range(0,len(str_in)):
        if str_in[idx] == "1":
            path[idx+1].append(i)
            indegree[i] += 1


que = []
for idx in range(N,0, -1):
    if indegree[idx] == 0:
        que.append(idx)



ans = []
cnt = N
while que:
    cur = que.pop(0)
    ans.append((cur, cnt))
    cnt -= 1
    for pa in range(len(path[cur])-1, -1, -1):
        indegree[path[cur][pa]] -= 1
        if (indegree[path[cur][pa]] == 0):
            que.append(path[cur][pa])
            que.sort(reverse=True)


ans.sort(key=lambda x: x[0])

if(len(ans) != N):
    print(-1)
else:
    for ori,i in ans:
        print(i, end=" ")

주석으로 달 설명

위상 정렬. 자꾸 근데 outdegree를 기준으로 정렬하는 문제가 많이 나오는 것 같다. 이상하리만치…