백준 3665 최종 순위

문제

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

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

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

---

코드

import java.io.*;
import java.sql.Array;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //테스트 케이스 개수 입력 받기
        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            //N 입력 받기
            int n = Integer.parseInt(br.readLine());

            //다른 node들을 한 번에 넣기 위한 임시 Set
            Set<Integer> temp=new HashSet<>();
            IntStream.range(1, n+1).forEach(temp::add);

            //노드 배열, 깊이 배열 선언
            Set<Integer>[] nodes=new Set[n+1];
            int[] degree=new int[n+1];
            
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<n; i++){
                //1등부터 n등까지
                int node = Integer.parseInt(st.nextToken());

                //자기 자신을 임시 Set에서 제거한 뒤 갱신해야 할 목록으로써 nodes[현재 노드]에 추가해준다
                temp.remove(node);
                nodes[node] = new HashSet<>();
                nodes[node].addAll(temp);
                
                //깊이는 1등이 0, n등이 n-1이다
                degree[node]=i;
            }

            //바뀐 등수 반영
            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());

                //노드 a가 b를 가지고 있으면 a가 b보다 등수가 높고 깊이가 낮다.
                //따라서 b가 갱신해야할 목록에 a를 추가해주고 a에서는 b를 제거한다
                //마지막으로 b의 깊이를 --, a의 깊이를 ++
                if(nodes[a].contains(b)){
                    nodes[a].remove(b);
                    nodes[b].add(a);

                    degree[a]++;
                    degree[b]--;
                }
                //노드 b가 a를 가지고 있으면 위와 반대
                else{
                    nodes[b].remove(a);
                    nodes[a].add(b);

                    degree[b]++;
                    degree[a]--;
                }
            }

            //정답 출력용 answer
            List<Integer> answer = new ArrayList<>();
            
            //큐에 깊이가 0인 노드부터 삽입한다.
            //1등부터 n등까지 탐색하기 위함
            Queue<Integer> q=new LinkedList<>();
            for(int i=1; i<degree.length; i++)
                if(degree[i]==0)
                    q.add(i);

            //큐에 두 개 이상의 노드가 있을 경우는 ?를 출력하기 위한 boolean 값
            boolean isDone=false;
            while(!q.isEmpty()){
                //큐에 노드가 1개가 아니라면 같은 순서의 노드가 두 개 이상이라는 뜻이므로 순서를 보장할 수 없다
                if(q.size()>1){
                    bw.write("?\n");
                    isDone=true;
                    break;
                }

                //노드를 꺼내서 answer에 추가해주고 갱신해야할 목록들의 깊이를 -1씩 해준다
                //만약 깊이가 0인 노드가 생긴다면 큐에 삽입
                int node=q.poll();
                nodes[node].forEach(o->{
                    if(--degree[o]==0)
                        q.add(o);
                });

                answer.add(node);
            }

            //?를 출력했다면 continue
            if(isDone)
                continue;

            //n개의 노드를 모두 방문했다면 정답 출력
            if(answer.size()==n)
                bw.write(answer.stream().map(String::valueOf).collect(Collectors.joining(" "))+"\n");
            else
                bw.write("IMPOSSIBLE\n");
        }

        bw.flush();
    }
}

---

해결 과정

1. 위상 정렬 문제인지 파악하는 것도 오래 걸렸다. 내가 알던 위상 정렬은 하나의 그래프로 나타낼 수 있는데, 그렇게 하면 두 노드 간의 순서를 바꾸기 매우 힘들었다.

2. 답을 보고 공부했다. 각 노드마다 후순위의 노드들을 모두 가지고 있고 그러면 두 노드 간의 순서를 바꾸기 쉽다.
   순서를 모두 바꾸고, 차수를 모두 변경해준 뒤 차수가 0인 노드부터 큐에 삽입해서 탐색한다.
   큐에 들어가는 순서대로 1등부터 n등까지이다. 다만 큐에 2개 이상의 노드가 있을 경우 같은 깊이가 2개이므로 어떤 노드가 해당 등수인지 알 수 없다.
   모든 노드를 방문하지 않고 끝난 경우에는 Cycle이 발생해서 그렇다. 이는 불가능한 경우이다.

3. 😁