b3665. 최종순위

 

https://www.acmicpc.net/problem/3665

 

 

 

📌 자바(Java)로 푸는 최종 순위 문제 - 백준 3665 🏆🔁

 

🔎 문제 개요

 

백준 3665번 - 최종 순위는 위상 정렬(Topological Sort)을 응용하는 문제입니다.

 

• 작년 순위가 주어지고,
• 올해 바뀐 순위 정보들이 입력되며,
• 그 정보를 바탕으로 올해의 최종 순위를 결정하는 문제입니다.

 

단,

 

• 순위를 정확히 하나로 정할 수 없다면 ? 출력
• 모순이 발생해서 순위를 정할 수 없다면 IMPOSSIBLE 출력

 

---

💡 예제 입력

1
5
5 4 3 2 1
2
2 4
3 1

 

💡 예제 출력

5 3 2 4 1

 

 

---

🛠 알고리즘 접근 방식

 

이 문제는 기본 위상 정렬에

✔ 순위가 바뀐 간선을 뒤집는 작업(reverse edge)

✔ 정점 진입 차수(indegree) 업데이트

✔ 위상 정렬 결과가 여러 개인지 또는 사이클이 있는지 판단

이 포함된 문제입니다.

 

---

🔹 Java 코드 핵심 흐름

 

 

1. 작년 순위를 기반으로 기본 그래프 생성

for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
        graph[arr[i]].add(arr[j]);  // 앞순위 → 뒷순위
    }
}

✔ 순위 리스트가 앞에 있을수록 더 높은 순위이므로

✔ 인접 리스트를 기준으로 간선 추가

 

 

2. 바뀐 순위 정보 반영 (간선 뒤집기)

if (graph[a].contains(b)) {
    graph[a].remove((Integer) b);
    graph[b].add(a);
} else {
    graph[b].remove((Integer) a);
    graph[a].add(b);
}

✔ a → b였던 간선을 b → a로 변경

✔ 반대의 경우도 마찬가지

✔ 순위 변경 정보를 반영해서 그래프를 수정

 

 

3. 위상 정렬 수행 + 결과 해석

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int j = 1; j <= N; j++) {
    if (indegree[j] == 0) {
        pq.offer(j);
    }
}

while (!pq.isEmpty()) {
    if (pq.size() > 1) uncertain = true;  // 가능한 순위가 여러 개
    int curr = pq.poll();
    result.add(curr);

    for (int next : graph[curr]) {
        indegree[next]--;
        if (indegree[next] == 0) pq.offer(next);
    }
}

✔ 진입 차수(indegree)가 0인 정점을 큐에 넣고 순서대로 방문

✔ 정답이 유일하지 않으면 ?,

✔ 사이클이 존재하면 방문 수가 N이 아님 → IMPOSSIBLE

 

---

🔍 출력 조건

if (result.size() != N) {
    System.out.println("IMPOSSIBLE");
} else if (uncertain) {
    System.out.println("?");
} else {
    for (int x : result) sb.append(x).append(" ");
    System.out.println(sb);
}

✔ 위상 정렬이 정상 종료되었는지

✔ 중간에 큐에 여러 노드가 들어간 적이 있는지

✔ 이 조건들을 통해 상황에 맞는 정답 출력

 

---

🏆 정리

 

 

✅ 핵심 포인트

 

• 위상 정렬을 기반으로 간선 뒤집기(순위 수정) 적용
• 결과가 한 가지가 아닌 경우 ? 처리
• 사이클로 인해 정렬이 불가능하면 IMPOSSIBLE 처리

 

 

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊