백준 3665번: 최종순위(Java, 그래프, 위상정렬)

☑️ 문제

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

✔️관련 알고리즘 개념

위상 정렬

☑️ 문제 분석

• 그림을 이용하여 문제를 입력하면 다음과 같다.

• 만약 위상 정렬을 적용하여 노드간의 순서가 잘 출력 될 것 같으면 노드간의 순서를 출력한다.
  • 하지만, 진입차수가 0인 차수가 없는 경우에는 정렬이 불가하므로 ‘IMPOSSIBLE’을 출력하고
  • 반면, 진입차수가 0인 차수가 존재하지만 여러개 있는 경우 정확한 순위를 매길 수 없으므로 ‘?’를 출력한다.

☑️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int[] lastRank;
    static ArrayList<ArrayList<Integer>> arrayList; 
    static int[] D;                                 // 진입차수
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int tc = 0; tc < t; tc++) {
            n = Integer.parseInt(br.readLine()); // 팀의 개수

            // 작년 순위
            lastRank = new int[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                lastRank[j] = Integer.parseInt(st.nextToken()); j 인덱스에 저장
            }

           
            arrayList = new ArrayList<>(n + 1);
            for (int j = 0; j <= n; j++) arrayList.add(new ArrayList<>());
            D = new int[n + 1];

            // 작년 순위를 인접리스트에 저장 
            for (int j = 1; j <= n; j++) {
                for (int k = j + 1; k <= n; k++) {
                    int u = lastRank[j]; 
                    int v = lastRank[k]; 
                    arrayList.get(u).add(v);
                    D[v]++;
                }
            }

            // 상대적인 등수가 바뀐 쌍의 수
            int m = Integer.parseInt(br.readLine());
            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                changeRank(a, b); 
            }

            // 최종 위상 정렬 적용하여 올해 순위 출력하기
            out.append(topologicalSort()).append('\n');
        }

        System.out.print(out.toString());
    }

    private static String topologicalSort() {
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (D[i] == 0) queue.offer(i);

        List<Integer> order = new ArrayList<>(n);
        boolean ambiguous = false;

        for (int step = 0; step < n; step++) {
            if (queue.isEmpty()) return "IMPOSSIBLE";  

            if (queue.size() > 1) ambiguous = true;     // 같은 시점의 후보가 2개 이상 → 모호

            int now = queue.poll();
            order.add(now);

            for (int next : arrayList.get(now)) {
                D[next]--;
                if (D[next] == 0) queue.offer(next);
            }
        }

        if (ambiguous) return "?";

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(order.get(i));
        }
        return sb.toString();
    }

    // a와 b팀의 상대적 순위 바꾸기 
    private static void changeRank(int a, int b) {
        // a -> b 가 있으면 b -> a 로 뒤집기
        if (arrayList.get(a).contains(b)) {
            arrayList.get(a).remove((Integer) b);
            D[b]--;
            arrayList.get(b).add(a);
            D[a]++;
        }
        // 없으면 b -> a가 있다고 보고 a -> b로 뒤집기
        else if (arrayList.get(b).contains(a)) {
            arrayList.get(b).remove((Integer) a);
            D[a]--;
            arrayList.get(a).add(b);
            D[b]++;
        }
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 다양한 예외 상황을 고려하여 코드를 작성하는 것이 어려웠다.