문제 상황
백준 1005번 문제를 풀다가 우선순위 큐를 사용해서 위상정렬을 구현했다. 코드를 완성하고 팀원과 비교해보니 둘 다 같은 답을 출력하는데, 우선순위 큐에 값을 넣는 부분의 코드 순서가 다르더라.
처음엔 그냥 스타일 차이라고 생각했는데, 자세히 보니 정렬 기준이 되는 값을 초기화하는 시점이 달랐다. 나의 실수를 기록하고, 이를 파고들어 정리하고자 한다.
코드 비교 : 어디가 다른가
// 내 코드
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.offer(i); // 우선순위 큐에 먼저 삽입
answer[i] = res[i]; // 나중에 정렬 기준값 초기화
}
}// 팀원의 코드
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
answer[i] = res[i]; // 먼저 정렬 기준값 초기화
q.offer(i); // 나중에 우선순위 큐에 삽입
}
}
두 코드 모두 결과적으로 같은 동작을 하는 것처럼 보인다. 하지만 이 순서 차이는 생각보다 중요했다.
근본 원인 : PriorityQueue와 힙의 관계
이 의문을 풀려면 Java의 PriorityQueue가 어떻게 구현되어 있는지 알아야 했다.
1) PriorityQueue의 내부 구조
Java의 PriorityQueue는 내부적으로 이진 힙(binary heap) 자료구조를 사용한다. 우선순위를 효율적으로 관리하기 위해 배열 기반의 완전 이진 트리 형태로 구현된 것인데, 이것이 핵심이다.
힙의 특징
- 완전 이진 트리 형태: 모든 레벨이 왼쪽부터 차곡차곡 채워짐
- Min-heap : 부모 노드 ≤ 자식 노드 (루트가 항상 최솟값)
- 배열 표현 : 인덱스
i에서- 왼쪽 자식 :
2*i + 1 - 오른쪽 자식 :
2*i + 2 - 부모 :
(i-1) / 2
- 왼쪽 자식 :
이 구조 덕분에 최솟값을 O(1)에 찾고, 삽입과 삭제도 O(log n)에 처리할 수 있다.
2) 힙이 우선순위를 유지하는 방식
여기가 핵심이다. 힙이 항상 우선순위 조건을 만족하려면 두 가지 핵심 연산을 수행해야 한다.
삽입할 때(Sift-Up)
- 새 원소를 배열 끝에 추가
- 부모와 비교해서 조건을 만족할 때까지 위로 올린다
- 올바른 위치를 찾을 때까지 반복
삭제할 때(Sift-Down)
- 루트(최솟값)를 제거
- 배열 마지막 원소를 루트 자리에 이동
- 자식들과 비교해서 조건을 만족할 때까지 아래로 내린다
- 올바른 위치를 찾을 때까지 반복
가장 중요한 포인트는 이것이다
이 연산들은 삽입과 삭제 순간에만 일어난다.
한 번 배치가 끝나면, 외부에서 아무리 값이 바뀌어도 힙은 그 변화를 감지하지 않는다는 뜻이다.
내가 놓친 부분
이제 내 실수가 무엇인지 명확해진다.
나는 무의식적으로 이렇게 가정했다
"인덱스
i를 큐에 넣고, 나중에answer[i]값을 업데이트하면 힘이 그 변화를 감지해서 자동으로 재배치하지 않을까?"
하지만 이건 완전한 오해였다.
내 코드의 실행 흐름
[초기 상태]
answer = [0, 0, 0, ...]
[Step 1] q.offer(i) 호출
├─ PriorityQueue: "이제 삽입합니다"
├─ answer[i]의 현재값 확인: 0
├─ Sift-Up 수행: 0 값 기준으로 배치
└─ 배치 완료 ✓
[Step 2] answer[i] = res[i] 실행
├─ answer 배열 값 변경 (0 → 5)
├─ PriorityQueue: (감지 안 함)
└─ 힙 구조 유지 (그대로)
팀원 코드의 실행 흐름
[Step 1] answer[i] = res[i] 실행
└─ answer 배열 값 세팅: 5
[Step 2] q.offer(i) 호출
├─ PriorityQueue: "이제 삽입합니다"
├─ answer[i]의 현재값 확인: 5
├─ Sift-Up 수행: 5 값 기준으로 배치
└─ 배치 완료 ✓
차이가 극명하다. 내 코드는 잘못된 기준(0) 으로 배치했고, 팀원 코드는 올바른 기준(5) 으로 배치했다. 나중에 내가 값을 바꿔도, 이미 정해진 힙 구조는 변하지 않는다.
왜 이 차이가 눈에 띄지 않았나
흥미로운 점은 두 코드 모두 같은 정답을 출력했다는 것이다.
이번 문제(ACM Craft)의 특수한 성질 때문인 것 같다. 위상정렬에서 여러 원소가 동시에 처리될 수 있는 상황에서, 초기 배치 순서가 조금 이상해도 최종 결과는 같을 수 있기 때문이다. 즉, 내 코드도 잘못된 배치에도 불구하고 우연히 맞는 답을 도출한 셈이다.
하지만 이건 운이 좋았던 것이지, 근본적인 해결책이 아니다. 다른 문제나 다른 상황에서는 이 순서 차이가 명백한 오류로 드러날 가능성이 높다.
올바른 사용 방식
이제 답은 명확하다.
정렬 기준이 되는 값을 먼저 초기화한 후, 우선순위 큐에 삽입한다.
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
answer[i] = res[i]; // 기준값 준비
q.offer(i); // 올바른 값 기준으로 삽입
}
}
이렇게 하면 Sift-Up이 수행될 때, 정렬 조건이 이미 올바르게 반영된 상태에서 시작된다. 의도한 대로 정확하게 동작한다.
결론 : 자료구조의 동작 원리를 무시하면 안 된다
이번 경험을 통해 얻은 교훈을 정리하면 이렇다.
1. PriorityQueue는 정렬된 리스트가 아니다
- 완전히 정렬된 상태를 유지하지 않는다
- 오직 루트가 최솟값이라는 조건만 보장한다
2. 힙의 배치는 삽입/삭제 순간에만 결정된다
- 외부에서 값이 바뀌어도 자동으로 재배치되지 않는다
- 한 번 Sift-Up이 끝나면, 그 이후 구조는 변하지 않는다
3. 삽입 시점이 모든 것을 좌우한다
- 그 순간의 값이 힙 구조 전체를 결정한다
- 정렬 기준이 되는 값은 반드시 삽입 전에 준비되어야 한다
"대충" 코드를 짜면 우연히 맞을 수도 있다. 하지만 자료구조의 원리를 제대로 이해하지 못하면, 언제든 그 우연이 깨질 수 있다. 이번 발견 덕분에 PriorityQueue를 더 정확하게 사용할 수 있게 되었고, 앞으로 비슷한 함정에 빠지지 않을 것 같다.
