정답 코드

import sys
import heapq
input = sys.stdin.readline

N = int(input())
c = [list(map(int, input().strip())) for _ in range(N)]

graph = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1)

# 방향: j가 i보다 앞선다 → j → i
for i in range(N):
    for j in range(N):
        if c[i][j] == 1:
            graph[j + 1].append(i + 1)
            in_degree[i + 1] += 1

heap = []
for i in range(1, N + 1):
    if in_degree[i] == 0:
        heapq.heappush(heap, -i)  # 최대 힙

label = [0] * (N + 1)
num = N

while heap:
    current = -heapq.heappop(heap)
    label[current] = num
    num -= 1
    for neighbor in graph[current]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            heapq.heappush(heap, -neighbor)

if num != 0:
    print(-1)
else:
    print(*label[1:])

이 문제는 위상정렬이 메인이다만 그거 외에도

고려할게 많아 풀어나갈수록 머리를 따땃하게 데워준다

위상 정렬 답게 여러가지 수열을 만들 수 있다만

여러 개일 경우 사전 순으로 제일 앞서야 한다

이 조건이 참으로 개처열받는다 할 수 있겠다

나같은 경우 이를 크게 고려하지 않고 처음에 코드를 짰다

오답 코드

import sys
input = sys.stdin.readline
import heapq

N = int(input())
# 0000100 이딴거 받기
c = [list(map(int, input().strip()))for _ in range(N)]

graph = [[] for _ in range(N + 1)]
in_degree = [0] * (N+1)


# 사전 순을 위해 힙 사용
for i in range(N):
    for j in range(N):
        # 1인곳의 index의 위치가 더 크단 뜻
        if c[i][j] == 1:
            # j가 i보다 등수가 높다는 뜻 → j → i
            graph[j + 1].append(i + 1)
            in_degree[i + 1] += 1

heap = []
for check in range(1, N + 1):
    if in_degree[check] == 0:
        heapq.heappush(heap, check)

label = [0] * (N + 1)
num = 1

while heap:
    current = heapq.heappop(heap)
    label[current] = num
    num += 1
    for neighbor in graph[current]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            heapq.heappush(heap, neighbor)
            
if num <= N:
    print(-1)
else:
    print(*label[1:])

좀 보면 알겠지만 위상 정렬 메커니즘 자체는 동일하다

실제로 넣어보아도 조건에 맞는 수열을 출력한다

그치만…

답이 여러 개일 경우에는 사전 순으로 제일 앞서는 것을 출력한다. <- 이 새끼 때문에 오답 처리 된다

왜 사전순이 아니냐에 대해선 이제 설명하겠다

오답 정답 갈리는 이유

힙에 푸쉬하는 방법에 따라서 갈린다 할 수 있다

오답 코드의 경우 작은 번호부터 힙에 넣고 라벨을 부여한다

이게 문제가 생겨버리는 이유는

작은 번호부터 처리한다는 거다

엥? 그게 왜?

그 이유는 예시로 설명하겠다

왜 실패하는가?

구린 코-드

heapq.heappush(heap, check)  # 최소 힙 (작은 번호 우선)
label[current] = num         # num = 1부터 증가

작은 번호부터 힙에 넣고, 작은 번호 먼저 라벨을 부여
label[i]는 i번 노드가 위상 정렬 결과에서 몇 번째에 오는지를 의미

예를 들어 진입차수 0인 노드가 2, 4, 5가 있다고 할 때:

이 코드는 작은 번호부터 처리해서
- 2 → label 1
- 4 → label 2
- 5 → label 3
그럼 결과는 [?, 1, ?, 2, 3]
즉, 2번 노드가 첫 번째, 4번이 두 번째, 5번이 세 번째가 돼버림

→ 2번이 맨 앞에 오면 안 되는 상황일 수도 있음
→ 사전순 정답보다 뒤로 밀리는 결과가 생김
→ ㅈ망

그럼 어떡하면 되는가?

생각보다 간단하다

작은 거 부터 해서 안되면 큰 거 부터 하면 된다

큰 번호부터 처리할 경우 작은 번호들이 남고 이럴 경우 자연스레 작은 번호가 앞쪽이 될 수 있다

예시를 확인해보자

쿨한 코-드

heapq.heappush(heap, -i)   # 최대 힙 (큰 번호 우선)
label[current] = num       # num = N부터 감소

큰 번호부터 먼저 처리해서 뒤쪽 라벨 부여
작은 번호가 최대한 뒤에 등장하지 않도록 함
label[i]가 작을수록 i는 더 앞 순서에 위치

큰 번호부터 먼저 꺼내서 큰 라벨을 준다
- 5 → label 5
- 4 → label 4
- 2 → label 3
그럼 label 배열이 [?, 3, ?, 4, 5]

→ 정답 배열은 label 오름차순 정렬 결과: 1 2 5 3 4
→ 작은 번호들이 가능한 앞쪽에 배치됨
→ 사전 순으로 앞서는 위상정렬 완성 q(≧▽≦q)

표로 요약

항목	첫 번째 코드 (실패 가능)	두 번째 코드 (정답 보장)
힙 방향	최소 힙 (`heapq.heappush(heap, i)`)	최대 힙 (`heapq.heappush(heap, -i)`)
라벨 부여 방식	1부터 증가	N부터 감소
작은 번호 처리 시점	먼저 처리 → 앞쪽 라벨	나중에 처리 → 작은 라벨
사전 순 결과	뒤로 밀릴 수 있음	항상 앞서는 결과
정답 보장	❌ (예제는 맞을 수 있으나 반례 존재)	✅ (항상 정답)