[JAVA] 백준 3665번 최종 순위

문제

올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.

 

올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

 

창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.

 

입력

첫째 줄에는 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

• 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)
• n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다.
• 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)
• 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.

출력

각 테스트 케이스에 대해서 다음을 출력한다.

• n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이

위상정렬 문제이다!

주의해야 하는 것은, 정점 두개의 의존관계가 바뀌어도 다른 정점들과의 의존관계는 바뀌면 안된다는 것이다.

머리를 굴려본 결과, 모든 정점에 대해서 다른 정점에 의존관계를 adjMatrix에 표시해주는 방법을 사용했다.

 

예를 들어 5-> 4-> 3-> 2-> 1의 순서가 있다고 하자.

5번 작업은 4번, 3번, 2번, 1번 작업보다 먼저 수행되어야 한다.

이를 표시하면 5->4, 5->3, 5->2, 5->1이 된다.

그래프로 표시하면 아래와 같다.

인접 행렬로 표현하면 아래와 같이 표현될 것이다.

정점	1	2	3	4	5
5	T	T	T	T	F

 

4번 작업은 3번, 2번, 1번 작업보다 먼저 수행되어야 한다.

이를 표시하면 4->3, 4->2, 4->1이 된다.

그래프로 표시하면 아래와 같다.

인접 행렬로 표현하면 아래와 같이 표현될 것이다.

정점	1	2	3	4	5
4	T	T	T	F	F
5	T	T	T	T	F

이 과정을 가장 마지막 정점까지 반복하면 이러한 모양의 그래프가 될 것이다.

인접 행렬로 표현하면 아래와 같이 표현될 것이다.

정점	1	2	3	4	5
1	F	F	F	F	F
2	T	F	F	F	F
3	T	T	F	F	F
4	T	T	T	F	F
5	T	T	T	T	F

이렇게 그래프를 만든 뒤, 문제에서 주어지는 정점 간의 관계만 수정해주면 된다.

예제에 있는 것처럼 2번, 4번의 정점의 관계가 바뀌었다고 하면 

정점	1	2	3	4	5
1	F	F	F	F	F
2	T	F	F	F	F
3	T	T	F	F	F
4	T	T	T	F	F
5	T	T	T	T	F

표시된 부분의 T를 F로, F를 T로 수정해주면 된다.

정점	1	2	3	4	5
1	F	F	F	F	F
2	T	F	F	T	F
3	T	T	F	F	F
4	T	F	T	F	F
5	T	T	T	T	F

예제에서 3번과 4번 정점의 관계도 변하였으니 수정하면 최종 인접행렬은 아래 처럼 된다.

정점	1	2	3	4	5
1	F	F	F	F	F
2	T	F	F	T	F
3	T	T	F	T	F
4	T	F	F	F	F
5	T	T	T	T	F

이것을 그래프로 나타내면 

이러한 그래프가 된다.

위 그래프는 사이클이 없으므로 위상 정렬이 가능하다. 

위상정렬을 진행하면 결과는 5->3->2->4->1이 되고 정답이 된다.

 

만약, 위의 과정을 진행했을 때 최종 그래프에 사이클이 존재하면 위상 정렬이 되지 않는 경우이므로 IMPOSSIBLE을 출력하면 된다.

 

사이클의 유무 판별 방법

구해진 위상 정렬 결과를 돌면서, <- 방향의 간선이 존재하는지 확인한다.

 

위상정렬 결과가 5->3->2->4->1 일 때

1번에서 4번, 3번, 3번, 5번으로 가는 간선이 있는지 확인한다.

4번에서 2번, 3번, 5번으로 가는 간선이 있는지 확인한다. 

2번에서 3번, 5번으로 가는 간선이 있는지 확인한다.

3번에서 5번으로 가는 간선이 있는지 확인한다.

 

위의 과정에서 간선이 모두 존재하지 않는 경우가 역방향으로 가는 간선이 없는 경우(<- 방향의 간선이 없는 경우), 즉 사이클이 존재하지 않는 경우가 된다. 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ3665 {

    static boolean [][] adjMatrix;
    static boolean [] visited;
    static int N;
    static List<Integer> order;

    static void dfs(int current){
        visited[current] = true;
        for (int i = 1; i <= N; i++) {
            if (adjMatrix[current][i] && !visited[i]){
                dfs(i);
            }
        }
        order.add(current);
    }

    static boolean isPossible() {
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                if (adjMatrix[order.get(j)][order.get(i)])
                    return false;
            }
        }
        return true;
    }

    static void topologicalSort() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if (!visited[i])
                dfs(i);
        }
        Collections.reverse(order);
        if (isPossible()){
            for (int i = 0; i < N; i++) {
                sb.append(order.get(i)).append(" ");
            }
        } else {
            sb.append("IMPOSSIBLE");
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine());
            adjMatrix = new boolean[N+1][N+1];
            visited = new boolean[N+1];
            order = new ArrayList<>();
            int[] origin_ranking = new int[N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                origin_ranking[i] = Integer.parseInt(st.nextToken());
            }
            for (int i = 1; i <= N; i++) {
                for (int j = i+1; j <= N; j++) {
                    adjMatrix[origin_ranking[i]][origin_ranking[j]]=true;
                }
            }
            int M = Integer.parseInt(br.readLine());
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                if (adjMatrix[a][b]){
                    adjMatrix[a][b]=false;
                    adjMatrix[b][a]=true;
                } else {
                    adjMatrix[a][b]=true;
                    adjMatrix[b][a]=false;
                }
            }
            topologicalSort();
        }
    }
}

결과

문제	결과	메모리	시간	언어	코드 길이
3665	맞았습니다!!	36324 KB	408 ms	Java 8	2745 B

http://boj.kr/0d85820b49a548ee94c2437c741c321b

공유 소스 보기