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

www.acmicpc.net/problem/3665

3665번: 최종 순위

 

 

 위상정렬문제인데 기존 문제보다 조금 복잡하다. 왜냐하면 보통의 위상정렬은 A가 B보다 앞에있다! 이런식으로 단순하게 하나씩만 관계를 설정하면 된다. 하지만 이번 문제는 순서가 미리 정해져 있으며, 순위의 선후관계가 바뀌는 경우다. 따라서 순위에 따라서 모든 관계를 추가해주어야 한다. 예를 들어, 5 4 3 2 1의 순위가 있다면 5의 경우는 4 3 2 1을 List<Integer>[]에 저장하고 inDegree는 0이다. 즉, 순위가 앞서있는 사람들이 뒤에 사람들의 정보를 가진다. 그래야 나중에 뒤에 순위로 순서이동이 가능하다.

 

 순위의 이동이 일어나는 경우, inDegree를 +1, -1로 바꿔주고, List<Integer>[]의 값 또한 서로 포함관계를 바꿔준다.

 

 마지막에 제대로 된 순위를 정할 수 있는지 확인한다. 기존에는 inDegree배열의 값이 0인 경우를 Queue에 담아서 검사하도록 했다. 이 때 많은 경우의 수 중에서 하나의 경우의 수를 뽑으면 되기 때문에 가능한 풀이법이다. 하지만 이 문제는 제대로 된 순서가 보장되지 않을 수 있다. 즉, inDegree의 값들이 중복되거나 0이 없는 등의 오류가 있는 것이다. 따라서 어떻게 이 순서를 보장하는 것을 확인할 것인가? 이는 while에서 해결하지 않고 for문으로 돌려서 정상적으로 종료되는지, 비정상적으로 종료되는지 확인 할 수 있다.

 

 

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int time=1;time<=T;time++) {
			int N = sc.nextInt();
			
			int[] inDegree = new int[N+1];
			int[] array = new int[N+1];
			for(int i=1;i<=N;i++) {
				array[i] = sc.nextInt();
			}
			
			List<Integer>[] list = new ArrayList[N+1];
			for(int i=1;i<=N;i++)
				list[i] = new ArrayList<>();
			
			for(int i=1;i<=N;i++) {
				int from = array[i];
				for(int j=i+1;j<=N;j++) {
					list[from].add(array[j]);
					inDegree[array[j]]++;
				}
			}
			
			int M = sc.nextInt();
			for(int i=0;i<M;i++) {
				int front = sc.nextInt();
				int back = sc.nextInt();
				
				if(list[front].contains(back)) {
					list[front].remove((Integer)back);
					list[back].add(front);
					inDegree[front]++;
					inDegree[back]--;
				} else {
					list[back].remove((Integer)front);
					list[front].add(back);
					inDegree[back]++;
					inDegree[front]--;
				}
			}
			
			StringBuilder sb = new StringBuilder();
			
			Queue<Integer> queue = new LinkedList<>();

			int cnt=0;
			for(int i=1;i<=N;i++) {
				if(inDegree[i]==0) {
					cnt++;
					queue.add(i);
				}
			}
			
			if(cnt>1) {
				System.out.println("?");
				continue;
			}
			
			int result=0;
			
			boolean isFinished = false;
			for(int i=1;i<=N;i++) {
				if(queue.isEmpty()) {
					System.out.println("IMPOSSIBLE");
					isFinished=true;
					break;
				}
				
				int from = queue.poll();
				result++;
				sb.append(from).append(" ");
				for(int to : list[from]) {
					inDegree[to]--;
					if(inDegree[to]==0) queue.add(to);
				}
			}
			if(isFinished==true) continue;
			
			System.out.println(sb.toString());
		}
	}

}