🏆 최종 순위
좀 어렵게 느껴졌던 위상 정렬 문제 ㅠ ㅠ
문제를 이해하는게 오래 걸렸다;;
문제
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다.
올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.
창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성하시오. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.
입력
첫째 줄에는 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
- 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)
- n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다.
- 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)
- 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.
출력
각 테스트 케이스에 대해서 다음을 출력한다.
- n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.
🔑 IDEA
일단 나동빈님의 강좌를 통해 위상 정렬의 컨셉을 이해하고 오자.
위의 포스팅을 정독하였다면,
문제에서 말하는 "?"를 출력하는 경우와 "IMPOSSIBLE"을 출력하는 경우에 대해 이해할 수 있을 것이다.
- "IMPOSSIBLE": 사이클이 발생하는 경우
- 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 위상 정렬을 하기 위해서는 시작점이 존재해야 하는데, 사이클이 존재하는 그래프에서는 시작점을 찾을 수가 없기 때문이다.
- "?": Queue에 두 개 이상의 원소가 들어있는 경우
- 어떤 순간에 Queue에 두 개 이상의 원소가 들어있다는 것은, 그들간에는 우위를 가릴 수가 없다는 뜻이다. 만약 문제에서 "가능한 순서가 여러가지일 경우, 그 중 하나를 출력한다." 라는 식의 조건이 있었다면, Queue에 두 개 이상의 원소가 들어있어도 상관없지만, 이 문제에서는 정확한 순서를 가릴 수 없는 경우 "?" 를 출력해야 한다.
위 상황을 이해한 뒤, 풀이를 시작하도록 한다.
우선, A가 B보다 높은 순위를 가질 경우, A→B로 방향을 설정한다.
그러면 첫 번 째 테스트 케이스(5 4 3 2 1) 의 경우 다음과 같은 방향 그래프가 만들어진다.
| 1 | 2 | 3 | 4 | 5 | |
| 1 | F | F | F | F | F |
| 2 | T | F | F | F | F |
| 3 | T | T | F | F | F |
| 4 | T | T | T | F | F |
| 5 | T | T | T | T | F |
동시에 모든 노드의 indegree 값을 배열에 저장하면 다음과 같다.
indegree[6] {0, 4, 3, 2, 1, 0} (0번 째 인덱스는 비움)
swap(int n1, int n2) 메서드를 이용해
입력으로 들어온 변경된 우선순위를 반영하고,
모두 반영하여 업데이트된 indegree와 방향그래프 행렬을 이용해 위상 정렬을 수행한다.
💡 나의 풀이
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Main {
static int N;
static int[] indegree;
static boolean[][] edges;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
for(int t=0; t<TC; t++) {
N = Integer.parseInt(br.readLine());
indegree = 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 = Integer.parseInt(st.nextToken());
indegree[num] = i;
for(int j=1; j<=N; j++) {
if(j!=num && !edges[j][num])
edges[num][j] = true;
}
}
int m = Integer.parseInt(br.readLine());
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int n1 = Integer.parseInt(st.nextToken());
int n2 = Integer.parseInt(st.nextToken());
swap(n1,n2);
}
System.out.println(topologicalSort());
}
}
private static String topologicalSort() {
Queue<Integer> queue = new LinkedList<>();
StringBuilder sb = new StringBuilder();
for(int i=1; i<=N; i++) {
//indegree가 0개인 정점을 찾는다.
if(indegree[i] == 0)
queue.offer(i);
}
//정점의 개수만큼 반복한다.
for(int i=1; i<=N; i++) {
//진행과정에서 사이클이 형성된 경우
if(queue.size() == 0) return "IMPOSSIBLE";
/* Queue에 저장된 정점이 2개 이상이면 그들간의 우선순위를 알 수 없다.
* 동시에 여러개의 원소가 진입한 상태이다.
* 일반적인 위상정렬이라면 어떤 것이든 상관없지만 이 문제는 그렇지 않다. */
if(queue.size() > 1) return "?";
int cur = queue.poll();
sb.append(cur + " ");
for(int j=1; j<=N; j++) {
if(edges[cur][j]) {
edges[cur][j] = false;
if(--indegree[j] == 0) queue.offer(j);
}
}
}
return sb.toString();
}
private static void swap(int n1, int n2) {
if(!edges[n1][n2]) {
edges[n1][n2] = true;
edges[n2][n1] = false;
indegree[n1]--;
indegree[n2]++;
}
else {
edges[n1][n2] = false;
edges[n2][n1] = true;
indegree[n1]++;
indegree[n2]--;
}
}
}
3665번: 최종 순위
올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에
www.acmicpc.net