[백준] 3665 최종 순위 - 순서가 정해져 있는 위상정렬

문제

---

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

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

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

 

 

 

풀이

---

위 문제는 딱 상대적인 순서를 보고 순위를 맞추라는 문제를 보고 위상정렬(Topological)을 사용하는 문제라는 것을 알았다.

 

하지만 기존의 문제들과 다른점은 이미 순위가 매겨져 있는 상태에서 순위를 매기는 것이다.

 

따라서 순위를 이미 위상 정렬의 순서로 정렬을 해야한다.

for(int i = 0 ; i < n ; i++) {
	int num = parseInt(st.nextToken());
	rank[num] = i;
	
	for(int j = 1 ; j <= n ; j++) {
		if(j != num && !edges[j][num]) {
			edges[num][j] = true;
		}
	}
}

위 코드는 해당 순위에 맞게 간선과 진입차수를 정렬하는 것이다.

 

1번째는 진입차수가 0 이고 간선은 모든 노드와 연결 돼 있다.

2번째는 진입차수가 1 이고 간선은 0번째를 제외한 노드와 연결 돼 있다.

이와 같은 순서로 미리 위상정렬에 맞는 순서로 초기화 시켜놓는다.

 

해당 순위가 올해 바뀐경우는 위상정렬의 간선과 진입차수를 조정해주어야한다.

간선의 방향은 반대로 바꿔준다. 진입차수는 -1 +1 을 각각 해준다.

 

 

static void swap(int u, int v) {
	if(edges[u][v]) {
		edges[u][v] = false;
		edges[v][u] = true;
		
		rank[u]++;
		rank[v]--;
	}else {
		edges[u][v] = true;
		edges[v][u] = false;
		
		rank[u]--;
		rank[v]++;
	}
}

 

 

위 상태로 진입차수와 간선을 이용해 위상정렬을 해주면 된다.

static String topologicalSort() {
	StringBuilder sb = new StringBuilder();
	
	Queue<Integer> queue = new LinkedList<>();
	
	for(int i = 1 ; i <= n ; i++) {
		if(rank[i] == 0) {
			queue.add(i);
		}
	}
	
	for(int i = 0 ; i < n ; i++) {
		if(queue.isEmpty()) {
			return "IMPOSSIBLE";
		}
		
		if(queue.size() > 1) {
			return "?";
		}
		
		int now = queue.poll();
		sb.append(now + " ");
		
		for(int j = 1 ; j <= n ; j++) {
			if(edges[now][j]) {
				edges[now][j] = false;
				
				if(--rank[j] == 0) {
					queue.add(j);
				}
			}
		}
	}
	
	return sb.toString();
}

이 때 조심해야하는 부분은 이경우는 해당 위치의 순서를 정확하게 모르게 될경우 ? 를 출력한다.

또, 일관성이 없는 데이터를 받은경우는 IMPOSSIBLE 을 출력한다.

 

이는 위의 위상정렬 코드를 확인하면,

• 해당 순위가 여러개인 경우에는 queue 의 크키가 2개 이상이 된다. 이럴경우는 ? 를 출력한다.
• n 개의 순위를 모두 매기기 전에 queue의 크기가 0 이 되면 일관성이 없는 데이터로 인해 문제가 생긴것이므로 IMPOSSIBLE 을 출력한다.

<전체코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static int t, n, m;
	static int[] rank;
	static boolean[][] edges;
	static StringBuilder answer = new StringBuilder();

	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		t = parseInt(br.readLine());
		while(t-->0) {
			n = parseInt(br.readLine());
			
			rank = new int[n + 1];
			edges = new boolean[n + 1][n + 1];
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < n ; i++) {
				int num = parseInt(st.nextToken());
				rank[num] = i;
				
				for(int j = 1 ; j <= n ; j++) {
					if(j != num && !edges[j][num]) {
						edges[num][j] = true;
					}
				}
			}
			
			m = parseInt(br.readLine());
			for(int i = 0 ; i < m ; i++) {
				st = new StringTokenizer(br.readLine());
				int u = parseInt(st.nextToken());
				int v = parseInt(st.nextToken());
				
				swap(u, v);
			}

			answer.append(topologicalSort() + "\n");
		}		
		
		System.out.println(answer);
	}
	
	static String topologicalSort() {
		StringBuilder sb = new StringBuilder();
		
		Queue<Integer> queue = new LinkedList<>();
		
		for(int i = 1 ; i <= n ; i++) {
			if(rank[i] == 0) {
				queue.add(i);
			}
		}
		
		for(int i = 0 ; i < n ; i++) {
			if(queue.isEmpty()) {
				return "IMPOSSIBLE";
			}
			
			if(queue.size() > 1) {
				return "?";
			}
			
			int now = queue.poll();
			sb.append(now + " ");
			
			for(int j = 1 ; j <= n ; j++) {
				if(edges[now][j]) {
					edges[now][j] = false;
					
					if(--rank[j] == 0) {
						queue.add(j);
					}
				}
			}
		}
		
		return sb.toString();
	}
	
	static void swap(int u, int v) {
		if(edges[u][v]) {
			edges[u][v] = false;
			edges[v][u] = true;
			
			rank[u]++;
			rank[v]--;
		}else {
			edges[u][v] = true;
			edges[v][u] = false;
			
			rank[u]--;
			rank[v]++;
		}
	}
}