[백준] 3665번 최종 순위

문제 설명

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

문제 풀이

• 위상 정렬을 이용하여 풀이하였다.
• 이전 해의 데이터를 이용하여 map[from][to] (from->to 순서가 맞으면 1, 아니면 0), inbound[n] (x->n인 순서의 갯수) 배열을 채우고 변경된 올해 데이터를 반영한다.
• 이후 map, inbound 배열을 통해 일반적인 위상 정렬 알고리즘을 수행한다.

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;

    public static int T, N, M;

    public static int[][] map;
    public static int[] arr, result;
    public static int[] inbound;


    public static void solve() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            boolean exitFlag = false;
            N = Integer.parseInt(br.readLine());
            //초기화
            map = new int[N+1][N+1];
            arr = new int[N];
            result = new int[N];
            inbound = new int[N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                //해당 인덱스 이전 모든 인덱스들과의 관계 정의
                for (int j = 0; j < i; j++) {
                    map[arr[j]][arr[i]] = 1;
                    inbound[arr[i]]++;
                }
            }
            M = Integer.parseInt(br.readLine());
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());
                if (map[from][to] == 1) {
                    map[from][to] = 0;
                    inbound[to]--;
                    map[to][from] = 1;
                    inbound[from]++;
                } else {
                    map[to][from] = 0;
                    inbound[from]--;
                    map[from][to] = 1;
                    inbound[to]++;
                }
            }

            //위상 정렬
            Queue<Integer> q = new LinkedList<>();
            for (int i = 1; i <= N; i++) {
                if (inbound[i] == 0)
                    q.add(i);
            }
			
            //문제가 없으면 N번만 수행된다. 
            for (int i = 0; i < N; i++) {
                //사이클 발생
                if (q.isEmpty()) {
                    exitFlag = true;
                    break;
                }
                int cur = q.poll();
                result[i] = cur;
                for (int j = 1; j <= N; j++) {
                    if (map[cur][j] != 1) continue;
                    if (--inbound[j] == 0)
                        q.add(j);
                }
            }

            if (exitFlag) bw.write("IMPOSSIBLE\n");
            else {
                for (int i = 0; i < N; i++)
                    bw.write(result[i] + " ");
                bw.write("\n");
            }
        }
    }

    public static void main(String[] args) throws IOException {
        solve();
        bw.flush();
    }
}