[BOJ] 백준 3665 최종 순위

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

 Input 

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

 

 Output 

5 3 2 4 1
2 3 1
IMPOSSIBLE

위상정렬 (Topological sort)

위상정렬 (Topological sort)

변동된 정보를 이용하여 새로운 순위를 출력하는 문제입니다.

※ 작년 순위가 오류없이 명확하게 주어지기 때문에 (기존 정렬 존재)

     데이터 일관성이 없어 "IMPOSSIBLE" 한 경우는 있더라도 (← 사이클 형성)

    확실한 순위를 찾을 수 없어서 "?" 출력하는 경우는 없습니다. 

    (= 위상정렬 결과가 여러개 나오지 않습니다.)

 

구현

문제의 핵심은 기준 순위와 변동된 정보를 어떻게 그래프로 반영할지 입니다!

- 인접행렬로 그래프 표현

- 진입차수를 이용한 위상정렬 이용.

- 확실한 순위를 정할 수 없는 경우 "?" 출력

   ; 진입차수=0으로 queue에 들어오는 정점의 개수가 1개여야 합니다.

     queue에 정점 2개 이상이 있는 경우 선행관계가 없기 때문에

     위상정렬 결과가 2개 이상 나올 수 있습니다.)

- 데이터의 일관성이 없어서 "IMPOSSIBLE" 출력

    ; 변동된 순위 정보로 사이클 형성 유무 판단

      그래프상 간선이 남아 있는데 queue에 들어있는 정점이 없는 경우입니다.

 

[첫번째 테스트 케이스] - 주어진 정보로 순위 갱신

1

5

5 4 3 2 1

2

2 4

3 4

 

---

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int n;
    static char[][] graph;
    static int[] indegree;
    static final int SUCCEESS = 0;
    static final int IMPOSSIBLE = 1;
    static final int NOT_DETERMINED = 2;
    static Queue<Integer> queue;
    static List<Integer> list;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = Integer.parseInt(sc.next());
        
        while(T-- > 0) {
            // 팀의 개수
            n = Integer.parseInt(sc.next());
            
            // 인덱스를 '1'부터 제어
            graph = new char[n+1][n+1];
            indegree = new int[n+1];
            // 작년 정보를 입력받는다.(순위별로)
            for(int i=1; i<=n; i++) {
                int team = Integer.parseInt(sc.next());
                for(int j=1; j<=n; j++) {
                    if(graph[team][j] == '\u0000') graph[team][j] = 'O';
                    if(graph[j][team] == '\u0000') graph[j][team] = 'X';
                }
                // 자기자신을 순환하지는 않는다.
                graph[team][team] = 'X';
                
                indegree[team] = i-1;
            }
            
            // 바뀐 등수의 개수
            int m = Integer.parseInt(sc.next());
            for(int i=1; i<=m; i++) {
                int x = Integer.parseInt(sc.next());
                int y = Integer.parseInt(sc.next());
                
                changeState(x,y);
            }
            
            queue = new LinkedList<>();
            list = new ArrayList<>();
            
            // 위상 정렬
            int answer = topological_sort();
            
            // 정답 출력
            sayAnswer(answer);
        }
    }
    
    private static void sayAnswer(int answer) {
        if(answer == SUCCEESS) {
            while(!list.isEmpty()) {
                System.out.print(list.remove(0) + " ");
            }
            System.out.println();
        }else if(answer == IMPOSSIBLE) {
            System.out.println("IMPOSSIBLE");
        }else if(answer == NOT_DETERMINED) {
            System.out.println("?");
        }
    }

    private static int topological_sort() {
        // 주어진 정점의 개수만큼 진행한다.
        for(int i=1; i<=n; i++) {
            // 자기자신으로 들어오는 간선의 개수가 0개인 정점을 찾는다.
            if(indegree[i] == 0) {
                queue.add(i);
            }
        }
            
        // 정점의 개수만큼 반복한다.
        for(int i=1; i<=n; i++) {
            /*Queue에 저장된 정점이 2개 이상이면 그들간의 우선순위를 알 수 없다.
              (동시에 여러개의 원소가 진입한 상태이다.)    
              (일반적인 위상정렬이라면 어떤 것이든 상관없지만 이 문제는 그렇지 않다.)*/
            if(queue.size() >= 2) {
                return NOT_DETERMINED;
            }else if(queue.size() == 0) {
                // 진행과정에서 사이클이 형성되었다는 것이다.
                return IMPOSSIBLE;
            }
            
            int curNode = queue.poll();
            // 나중에 정상일 때 순위를 출력하기 위해 저장해둔다.
            list.add(curNode);

            // 모든 원소에 대해서 연결된 정점을 확인하다.
            for(int y=1; y<=n; y++) {
                // 간선이 존재한다면 연결을 끊어주고 indegree 개수도 줄여준다.
                if(graph[curNode][y] == 'O') {
                    graph[curNode][y] = 'X';
                    indegree[y]--;
                    // 그 과정에서 자기자신에게 들어오는 간선의 개수가 0개이면 queue에 넣어준다.
                    if(indegree[y] == 0) {
                        queue.add(y);
                    }
                }
            }
        }
        return SUCCEESS;
    }
    private static void changeState(int x, int y) {
        if(graph[x][y] == 'O') {
            graph[x][y] = 'X';
            graph[y][x] = 'O';
            indegree[x]++;
            indegree[y]--;
        }else {
            graph[x][y] = 'O';
            graph[y][x] = 'X';
            indegree[x]--;
            indegree[y]++;
        }
    }
}