[BOJ 3665] 최종 순위 (Java)

문제

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

3665번: 최종 순위

 

풀이

위상 정렬 알고리즘으로 풀 수 있다. 

 

예시

1. 작년 순위 정보를 저장한다.

작년 순위
5 -> 4 -> 3 -> 2 -> 1

인접 노드에 대한 정보를 담을 자료 구조를 생성한다.

나는 ArrayList<Integer>[] adjs = new ArrayList[] 을 이용하였다. 

 

이 때, 중요한 것은 해당 팀보다 순위가 낮은 모든 팀의 정보를 넣어야 한다.

adjs[5] 에는 4, 3, 2, 1 정보가 들어간다. 

adjs[4] 에는 3, 2, 1

adjs[3] 에는 2, 1

adjs[2] 에는 1

 

그리고 indegree 정보도 갱신해 준다. 

예를 들어 4팀은 5에서만 간선이 들어오므로 indegree가 1

1팀은 5, 4, 3, 2팀에서 모두 간선이 들어오므로 indgree가 4가 된다.

 

2. 순위가 바뀐 순서쌍을 적용한다.

2, 4

3, 4 

팀의 순위가 바뀌었다. 

작년 순위 정보에서 해당 정보를 찾아서 순서를 바꿔준다. 

이 때 indegree도 갱신한다.

 

3. 위상정렬 알고리즘을 적용한다. 

Indegree가 0인 노드가 start 노드가된다.

만약 indegree가 0인 노드가 2개 이상일 경우, 순위를 확실하게 정할 수 없으므로 정렬을 중지하고 "?"를 출력한다. 

만약 중간에 indegree가 0인 노드가 없는 경우 데이터의 일관성이 없어 정렬이 제대로 이루어지지 않았으므로 "IMPOSSIBLE"을 출력한다. 

나머지 경우 정렬된 순위를 출력한다.

 

소스코드

package topologicalsort;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ3665 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t < T; t ++){

            int N = Integer.parseInt(br.readLine());

            // 인접 노드를 담을 자료 구조 생성
            ArrayList<Integer>[] adjs = new ArrayList[N+1];
            for(int i = 0; i <= N; i++){
                adjs[i] = new ArrayList<Integer>();
            }

            // 작년 랭크 input 처리
            int[] rank = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i++){
                rank[i] = Integer.parseInt(st.nextToken());
            }

            // indegree 자료구조 생성
            int[] indeg = new int[N+1];

            // 작년 순위에 대해 인접노드 정보 생성
            // 5, 4, 3, 2, 1 ?
            // 5 - 4, 3, 2, 1
            // 4 - 3, 2, 1
            // 3 - 2, 1
            // 2 - 1
            for(int i = 0; i < N-1; i++){
                for(int j = i+1; j < N ; j++){
                    adjs[rank[i]].add(rank[j]);
                    indeg[rank[j]]++;
                }
            }

            // 바뀐 순서쌍 Input 받기
            int C = Integer.parseInt(br.readLine());
            for(int j = 0; j < C; j++){
                st = new StringTokenizer(br.readLine());
                Integer A = Integer.parseInt(st.nextToken());
                Integer B = Integer.parseInt(st.nextToken());
                if(adjs[A].contains(B)){
                    adjs[A].remove(B);
                    adjs[B].add(A);
                    indeg[A]++;
                    indeg[B]--;
                } else {
                    adjs[B].remove(A);
                    adjs[A].add(B);
                    indeg[B]++;
                    indeg[A]--;
                }
            }

            // topological sort 시작
            // indegree가 0인 것부터 시작
            Queue<Integer> que = new LinkedList<Integer>();
            for(int i = 1; i <= N; i++){
                if(indeg[i] == 0){
                    que.offer(i);
                }
            }

            int cnt = 0;
            StringBuilder sb = new StringBuilder();
            while(!que.isEmpty()){
                if(que.size() > 1) {
                    // 순위를 정할 수 없음
                    bw.write("?" + "\n");
                    break;
                }
                int node = que.poll();
                sb.append(node+ " ");
                cnt++;
                for(int adj : adjs[node]){
                    indeg[adj]--;
                    if(indeg[adj] == 0){
                        que.offer(adj);
                    }
                }
            }
            if(cnt != N){
                bw.write("IMPOSSIBLE" + "\n");
            } else {
                bw.write(sb.toString()+"\n");
            }
        }
        bw.flush();
    }
}