[백준] 3665. 최종 순위 (Java)

Jisu Nam·2023년 2월 9일
0

코딩테스트

목록 보기
12/12

🔍 문제


올해 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"을 출력한다.

🔑 풀이


순위를 판별할 수 없는 경우는 다음 두 가지와 같다.

  • IMPOSSIBLE : 사이클이 발생하는 경우
    위상 정렬을 할 수 있는 조건은 사이클이 없는 그래프인 DAG(Directed Acyclic Graph)에만 적용할 수 있다. 사이클이 발생하면, 사이클이 발생하는 구간에서 시작점(진입 노드의 수가 0인 노드)을 찾을 수 없기 때문에, 위상 정렬로의 구현이 불가능하다.
  • ? : 진행 과정에서 큐에 동시에 2개 이상의 원소가 들어가는 경우
    즉, 큐 내부에 저장된 원소들끼리 우위를 가릴 수 없다는 말과 같다. 문제에서 정확한 순위를 요구하기 때문에 이 경우 예외 처리를 해야 한다.

edges 배열을 통해 순위를 판별하기 위한 정보를 저장한다.
edges[i][j] : i가 j보다 순위가 높은 경우 true
문제의 테케 1번의 작년 순위를 예시로, edges 배열엔 다음과 같이 저장된다.

012345
0
1FFFFF
2TFFFF
3TTFFF
4TTTFF
5TTTTF

이를 정리해서, 위 정보를 기준으로 진입 노드 수 정보를 저장하는 inDegree배열에는 다음과 같은 값이 저장된다.
inDegree = {0, 4, 3, 2, 1};

그럼 올해 순위에 대해 정보를 어떤식으로 저장하면 될까?
swap(a,b)를 통해 만약 a가 b보다 순위가 높다면 edges[a][b] = true, edges[b][a] = false 이기 때문에, 둘의 상대 순위를 바꾸어줘야 하므로 edges[a][b]=false, edges[b][a]=true로 변경한다.
그렇게 되면 진입 노드 수 정보도 달라지는데
b의 진입 노드가 하나 줄고, a의 진입 노드가 하나 증가하므로 indegree[b]--; indegree[a]++;을 해주면 된다.

위 과정이 끝나면, 변경된 inDegree, edges 배열을 통해 위상 정렬을 수행하면 된다.

📝 CODE


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

public class Main {
    static int T, N, M;
    static int[] inDegree;
    static boolean[][] edges;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        T = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        for(int t=1;t<=T;t++) {
            N = Integer.parseInt(br.readLine());
            inDegree = new int[N+1];
            edges = new boolean[N+1][N+1];
            st = new StringTokenizer(br.readLine());
            for(int i=0;i<N;i++) {
                int currTeam = Integer.parseInt(st.nextToken());
                inDegree[currTeam] = i;
                for(int j=1;j<=N;j++)
                    if(j!=currTeam && !edges[j][currTeam]) edges[currTeam][j] = true;
            }
            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());
                swap(a, b);
            }
            sb.append(topologySort()).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        br.close();
    }

    static String topologySort() {
        Queue<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        for(int i=1;i<=N;i++) {
            if(inDegree[i] == 0) q.add(i);
        }

        for(int i=1;i<=N;i++) {
            // 사이클 발생
            if(q.size() == 0) return "IMPOSSIBLE";
			
            // 정확한 우위를 가릴 수 없음
            if(q.size() > 1) return "?";

            int curr = q.poll();
            sb.append(curr).append(" ");

            for(int j=1;j<=N;j++)
                if(edges[curr][j]) {
                    edges[curr][j] = false;
                    if(--inDegree[j] == 0) q.add(j);
                }
        }

        return sb.toString();
    }

    static void swap(int a, int b) {
    	// 상대적 순위 바꾸어주기
        if(!edges[a][b]) {
            edges[a][b] = true;
            edges[b][a] = false;
            inDegree[a]--;
            inDegree[b]++;
        } else {
            edges[b][a] = true;
            edges[a][b] = false;
            inDegree[b]--;
            inDegree[a]++;
        }
    }
}
profile
BE Developer

0개의 댓글