[백준][JAVA] BOJ 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"을 출력한다.

예제 입력

3
5
5 4 3 2 1
2
2 4
3 4
3
2 3 1
0
4
1 2 3 4
3
1 2
3 4
2 3

예제 출력

5 3 2 4 1
2 3 1
IMPOSSIBLE

 

 

문제 풀이📝

---

뭔가 DFS로 푸는 풀이가 생각나서 구현하려고 했는데, 구현도 만만치 않고 아무리 생각해도 시간초과가 날 것 같아서 알고리즘 분류를 확인했다.

위상정렬을 이용하면 됨을 깨달았지만, 적용하는 방법을 떠올리는 데에 많은 어려움이 있어서 다른 분의 풀이를 참고하였다.

https://escapefromcoding.tistory.com/207

[ 백준 / 3665 ] 최종 순위 ( 자바 )

 

일단 위상정렬에 대한 개념이 부족하여서 따로 공부를 했다.

단순하게 말하자면, 선후관계가 존재하는 그래프에서의 탐색을 위한 알고리즘이다.

(이에 대한 내용은 다음에 게시글로 정리해보려고 한다)

 

그러나 해당 문제에서는 정해진 선후관계에서 변화가 일어나기 때문에,

먼저 각각의 순위에 따른 모든 가능한 선후관계를 고려해주어야 한다.

5, 4, 3, 2, 1의 입력이 들어왔다면,

5의 뒤에 올 수 있는 팀들은 4, 3, 2, 1이 되고 5를 가리키는 다른 노드는 존재하지 않으므로 진입차수는 0이 된다.

그 후에는, 변경된 선후관계를 입력받아 기존의 그래프 방향을 수정해준다.

수정된 방향에 따라 진입차수도 증가/감소 시킨다.

마지막으로 순위를 유추한다. 이 때 총 3가지의 경우가 존재한다.

1) 진입차수가 0인 노드가 여러 개 존재

• 시작지점이 여러 개이므로 어떤 시작지점을 선택하냐에 따라 결과가 달라진다. 고로 정답을 특정할 수 없다.
• "?"를 출력한다.

2) 진입차수가 0인 노드가 존재하지 않음

• 모든 노드를 방문하지 않았음에도 불구하고, 더 이상 진입차수가 0인 노드가 없어 진행이 불가능하다.
• 이는 잘못된 정보로 인한 오류가 발생한 상황으로 "IMPOSSIBLE"을 출력한다.

3) 모든 노드를 무사히 방문

• 위상정렬한 결과를 출력한다.

 

구현🛠️

---

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

// 최종 순위
public class Main_3665 {

    static int T;
    static int N, M;
    static int[] origin;
    static int[] inDegree;  // 진입차수
    static Set<Integer>[] graph;
    static Queue<Integer> q;

    static StringBuilder answer;


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());
        answer = new StringBuilder();
        for (int t = 0; t < T; t++) {

            N = Integer.parseInt(br.readLine());
            origin = new int[N + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            // 작년 순위를 입력받는다
            for (int i = 1; i < N + 1; i++) {
                origin[i] = Integer.parseInt(st.nextToken());
            }

            // 작년 순위를 기반으로 방향 그래프를 생성한다
            graph = new HashSet[N + 1];
            inDegree = new int[N + 1];
            for (int i = 1; i < N + 1; i++) {
                graph[i] = new HashSet<>();
            }
            // 선후관계 변경이 있으므로, 가능한 모든 관계를 추가해준다.
            for (int i = 1; i < N + 1; i++) {
                int from = origin[i];
                for (int j = i + 1; j < N + 1; j++) {
                    graph[from].add(origin[j]);
                    inDegree[origin[j]]++;  // 해당 팀의 진입차수를 증가시켜준다.
                }
            }

            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());

                // 선후관계를 변경해준다
                swap(from, to);
            }

            answer.append(bfs()).append("\n");
        }
        System.out.println(answer);
    }

    // 선후관계 변경
    static void swap(int from, int to){

        if (graph[from].contains(to)){
            graph[from].remove(to);
            graph[to].add(from);
            inDegree[from]++;
            inDegree[to]--;
        } else {
            graph[to].remove(from);
            graph[from].add(to);
            inDegree[from]--;
            inDegree[to]++;
        }
    }

    static String bfs(){
        q = new ArrayDeque<>();

        for (int i = 1; i < N + 1; i++) {
            // 진입차수가 0인 노드들 찾기 -> 시작지점이 될 수 있는 것들
            if (inDegree[i] == 0){
                q.offer(i);
            }
        }

        // 만약 시작지점이 여러 개라면 -> 정답을 특정할 수 없다.
        if (q.size() > 1){
            return "?";
        }

        StringBuilder sb = new StringBuilder();
        // while문이 아닌 for문을 사용하여 오류인 경우를 검출한다
        for (int i = 1; i < N + 1; i++) {

            // 모든 노드를 순회하지 못한 경우 -> 오류가 있다는 뜻
            if (q.isEmpty()){
                return "IMPOSSIBLE";
            }

            // queue의 노드를 꺼낸다
            int from = q.poll();
            sb.append(from).append(" ");

            // 진입차수를 재조정한다 (간선 제거)
            for (int to : graph[from]) {
                inDegree[to]--;
                // inDegree가 0인 노드들을 queue에 넣는다
                if (inDegree[to] == 0){
                    q.offer(to);
                }
            }
        }

        return sb.toString();
    }
}

 

 

실행결과✅

---