[BOJ]-3665 최종순위

📌 문제 정보

• 문제 번호: BOJ 3665
• 문제 이름: 최종순위
• 난이도: Gold
• 분류: 위상정렬
  https://www.acmicpc.net/problem/3665

---

🧩 문제 요약

• 주어지는 입력

test_case = 테스트 케이스의 수,
n = 팀의 수,
T(i)= 작년에 i등을 한 팀의 번호
m = 상대적인 등수가 바뀐 쌍의 수
ai, bi = 상대적인 등수가 바뀐 두 팀

• 무엇을 구해야 하는지

상대적인 등수의 변화를 확인하여 올해의 순위를 1등팀부터 순서대로 출력
단 확실한 순위를 찾을 수 없다면 "?"
순위를 정할 수 없는 경우에는 "IMPOSSIBLE" 출력

---

💡 접근 아이디어

• 처음 떠올린 방법

기본적인 위상 정렬 알고리즘에서
순위를 확실하게 정할 수 없는 경우와
불가능한 경우를 생각해보는 문제라고 느꼈음.

---

🛠️ 해결 전략

구현 흐름을 단계별로 정리합니다.

핵심 로직(점화식 / 이동 규칙)

1. 순위에 따라 각 팀의 inDegree와 next를 지정한다.
2. m번 만큼 반복하여 a(i), b(i)의 inDegree와 next를 수정한다.
3. 정점을 확인하여 전부 정점에 도달했으면 출력
3-1. 아니면 케이스에 따라서 각 케이스에 맞는 문자열을 출력한다.

---

⚠️ 주의할 점

풀이 중 헷갈리거나 실수하기 쉬운 부분입니다.

• a(i)와 b(i) 처리

상대적인 순서 변경이기 때문에 A와 B의 대소 비교를 해서 각 케이스마다 다르게 작동해야 한다. A가 B보다 작년 등수가 컸던 경우에는 B의 inDegree를 감소시켜야 하고 A를 증가시켜야 한다.

---

## ✅ 코드
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Node {
        int idx;
        int indegree=0;
        HashSet<Integer> next = new HashSet<>();

        Node() {}

        Node (int idx) {
            this.idx = idx;
        }
    }

    static int n;
    static Node [] nodes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        for (int i=0;i<t;i++) {

            n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());

            nodes = new Node[n];
            for (int j=0;j<n;j++) nodes[j] = new Node();

            for (int j=0;j<n;j++) {
                int idx = Integer.parseInt(st.nextToken());
                nodes[j].idx = idx;
                nodes[j].indegree = j;

                // idx는 1부터 n까지 숫자이기 때문에 배열에 사용하기 위해 -1을 함.
                for (int k=j-1;k>=0;k--) {
                    nodes[k].next.add(idx-1);
                }
            }

            // 인덱스 번호로 정렬 => nodes[0] = idx : 1, nodes[1] = idx : 2번이 옴.
            Arrays.sort(nodes, (o1, o2) -> {
                return o1.idx - o2.idx;
            });

            int m = Integer.parseInt(br.readLine());
            for (int j=0;j<m;j++) {
                st = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(st.nextToken())-1;
                int b = Integer.parseInt(st.nextToken())-1;

                if (nodes[a].next.contains(b)) {
                    nodes[b].indegree--;
                    nodes[a].indegree++;
                    nodes[b].next.add(a);
                    nodes[a].next.remove(b);
                } else {
                    nodes[a].indegree--;
                    nodes[b].indegree++;
                    nodes[a].next.add(b);
                    nodes[b].next.remove(a);
                }
            }
            System.out.println(solve());
        }
    }

    static String solve() {
        Queue<Node> q = new ArrayDeque<>();
        for (int j=0;j<n;j++) {
            if (nodes[j].indegree == 0) q.add(nodes[j]);
        }

        boolean [] v = new boolean[n];
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            if (q.size() > 1) {
                return "?";
            }
            Node node = q.poll();
            v[node.idx-1] = true;
            sb.append(node.idx).append(' ');

            for (int prev : node.next) {
                nodes[prev].indegree--;
                if (nodes[prev].indegree == 0)
                    q.add(nodes[prev]);
            }
        }
        if (check(v)) return sb.toString();
        return "IMPOSSIBLE";
    }
    static boolean check(boolean [] v) {
        for (int i=0;i<n;i++) {
            if (!v[i]) return false;
        }
        return true;
    }
}