[BOJ] 3665. 최종 순위

위상정렬을 이용하여 풀었던 그래프문제이다.

이 문제를 맨처음 접했을 때 각 노드끼리의 순위가 존재하고 싸이클이 없기에 위상정렬을 사용해보았다. 맨처음 문제를 접근을 다음과 같이해보았다. 만일 1등, 2등, 3등, 4등이 존재한다면 4등->3등, 3등->2등, 2등->1등 이런식으로 그래프를 그려보았다. 하지만 이 문제는 순위가 뒤바뀌는 경우가 있는데 맨처음 내가 적용한 방식은 순위가 뒤바뀌는 것을 처리해주지 못하기에 그래프를 새롭게 그려보았다. 즉, 4등->3등, 4등->2등, 4등->1등, 3등->2등, 3등->2등, 2등->1등과 같이 순위가 낮은것이 자기보다 높은 순위를 모두 볼수 있도록 그래프를 그리는 방식을 수정하였다. 이런 방식을 통해 순위가 바뀌는 경우도 처리해주었고, 그래프를 새로그린다음에 위상정렬을 하였다.

이 문제에서는 순위가 애매해지는 "?"와 모순이 생기게 되는 "IMPOSSIBLE"을 처리해주는 부분이 있다. 순위가 애매해지는 경우는 위상정렬을 돌면서 동순위가 생기게 되는 경우인데 그 경우는 queue에서 하나를 뽑았을 때 queue에 남아있다면 애매해지는 방식으로 처리했다. 모순이 생기게 되는 경우는 위상정렬을 노드의 갯수만큼 못도는 경우 애매하게 처리하였다.

package algostudy2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main_bj_3665_최종순위 {
    static int N;
    static int[] indegree;
    static int[][] map;
    static int[] oldRank;
    static int[] newRank;
 
    static Queue<Integer> queue;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
 
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
 
            oldRank = new int[N + 1];
 
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                oldRank[i] = Integer.parseInt(st.nextToken());
            }
 
            initData();
 
            int change = Integer.parseInt(br.readLine());
            for (int i = 0; i < change; i++) {
                st = new StringTokenizer(br.readLine());
 
                int num1 = Integer.parseInt(st.nextToken());
                int num2 = Integer.parseInt(st.nextToken());
 
                //순위를 바꾸는 작업
                if (map[num1][num2] == 1) {
                    map[num1][num2] = 0;
                    indegree[num2]--;
                    map[num2][num1] = 1;
                    indegree[num1]++;
                } else {
                    map[num2][num1] = 0;
                    indegree[num1]--;
                    map[num1][num2] = 1;
                    indegree[num2]++;
                }
            }
 
            int curRank = topological();
 
            if (curRank == 0) {            //정상적인 경우
                for (int i = 1; i <= N; i++) {
                    sb.append(newRank[i] + " ");
                }
                sb.append("\n");
            } else if (curRank == -1) {        //순위가 애매한 경우
                sb.append("?\n");
            } else {                    //모순이 생기는 경우
                sb.append("IMPOSSIBLE\n");
            }
        }
        System.out.print(sb.toString());
    }
 
    static void initData() {
        indegree = new int[N + 1];
        map = new int[N + 1][N + 1];
 
        for (int index1 = 1; index1 <= N - 1; index1++) {
            for (int index2 = index1 + 1; index2 <= N; index2++) {
                int end = oldRank[index1];
                int start = oldRank[index2];
 
                map[start][end] = 1;
                indegree[end]++;
            }
        }
    }
 
    static int topological() {
        int curRankIndex = N;
        newRank = new int[N + 1];
 
        queue = new LinkedList<>();
 
        for (int i = 1; i <= N; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
 
        while (!queue.isEmpty()) {
            int cur = queue.poll();
 
            //하나를 뻇는데도 queue에 남아있다면 애매한 경우
            if (queue.size() > 0) {
                return -1;
            }
 
            newRank[curRankIndex] = cur;
            curRankIndex--;
 
            for (int i = 1; i <= N; i++) {
                if (map[cur][i] == 1) {
                    int next = i;
 
                    indegree[next]--;
 
                    if (indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }
 
        }
 
        return curRankIndex;
    }
}