[Java] 백준 3665번 : 최종 순위

1. 문제

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

3665번: 최종 순위

 

 

2. 풀이과정

1. 우선 순위 관계를 boolean 2차원 배열에 저장한다. 이때, 1~N까지인 팀이 있으므로 첫 번째 요소를 찾기위해 제일 첫 번째를 0으로 지정하고 시작했다.

2. 위상 정렬으로 자신의 앞에 아무것도 없는 노드가 다음 순서가 된다.

3. 아직 방문하지 않은 모든 노드의 앞에 누군가가 있다면, 순위를 예측할 수 없는 경우이다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int p[];
    static StringBuilder result;
    static boolean relation[][];

    public static void swap(int n1, int n2){
        if(relation[n2][n1]){
            int temp = n1;
            n1 = n2;
            n2 = temp;
        }
        relation[n1][n2] = false;
        p[n2]--;
        relation[n2][n1] = true;
        p[n1]++;
    }

    public static void sort(int n, int now){
        StringBuilder sb = new StringBuilder();
        int cnt = 0, nextCnt = 0;

        while(cnt < n){
            p[now] = -1;//방문체크
            int temp = now;
            nextCnt = 0;
            for(int i=0; i<=n; i++){
                if(!relation[temp][i] || --p[i]!=0){ continue;}
                now = i;
                nextCnt++;
            }
            if(nextCnt != 1){
                result.append("IMPOSSIBLE\n");
                return;
            }
            sb.append(now).append(" ");
            cnt++;
        }
        result.append(sb.toString()).append("\n");
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        result = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        while(T-- > 0){
            int n = Integer.parseInt(br.readLine());
            p = new int[n+1];
            relation = new boolean[n+1][n+1];

            int order[] = new int[n+1];
            order[0] = 0;
            st = new StringTokenizer(br.readLine());
            for(int i=1; i<=n; i++){
                order[i] = Integer.parseInt(st.nextToken());
                for(int j=0; j<i; j++){
                    p[order[i]]++;
                    relation[order[j]][order[i]] = true;
                }
            }

            int m = Integer.parseInt(br.readLine());
            for(int i=0; i<m; i++){
                st = new StringTokenizer(br.readLine());
                int n1 = Integer.parseInt(st.nextToken());
                int n2 = Integer.parseInt(st.nextToken());
                swap(n1, n2);
            }
            sort(n, 0);
        }

        System.out.println(result.toString());
    }
}

 

 

결과