백준 | 3655번. 최종 순위 - 위상 정렬 문풀

⬛ 백준 3655번. 최종 순위 - 위상 정렬 문풀

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

3665번: 최종 순위

문제

올해 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"을 출력한다.

---

💚 문제 접근 방식

• 이 문제는 작년 1~N등까지의 정보로 그래프를 먼저 형성한 뒤, M개의 뒤바뀐 등수를 반영하여 기존의 간선을 remove처리 후 반대 방향의 간선을 add 처리한 뒤 위상정렬 알고리즘을 수행하면 풀리는 문제인데, 보통의 문제보다 까다롭기 때문에 주의할 점이 많다.

1) ? 출력 : 위상 정렬 수행 과정에서 큐에 동시에 2개 이상의 정점이 있다면 순서가 여러개가 될 수 있어서 확실한 순위를 찾을 수 없는 경우가 된다. 이는 위상 정렬을 하기위한 한번의 순회에서, indegree-- 를 진행했을 때, 진입차수(in degree)가 0이되는 정점이 2개 이상 존재한다는 것을 의미한다.

2) IMPOSSIBLE 출력 : 사이클 없는 위상정렬 수행 과정은 N번의 반복으로 끝나야 하는데, answer에 담긴 순서 size가 N개가 아니라면 사이클이 생겼다는 말이다. 위상 정렬 과정에서 사이클이 생긴 그래프를 순회하면 방문하는 정점의 수가 n개보다 작다. cycle을 이루는 내부의 정점들의 indegree가 0이 될 수 없기 때문에 Q에 담기지 못한다. 따라서 처리할 수 있는 정점이 N개 보다 작아지는 것이다. 

- 위의 두 가지 사항을 주의해서 풀어야 하고, 나머지는 기존 정보로 그래프 형성 한 뒤, M개의 바뀐 등수 처리를 위해 기존 간선 제거 후 (방향 반대의) 새 간선 삽입 처리 해두면 된다.

- 이 상태의 graph에 접근해서 위상 정렬을 수행할 때, 정상적으로 사이클 없이 순서 결정 가능한 위상 정렬 대상이라면 정확히 N번 동안 회전할 것이고, 순서를 확실하게 알 수 있는 경우는 매번 Queue에 담긴 size() == 1일 것이므로 위의 엣지 케이스를 처리해서 문제가 요구하는 대로 출력하는 것이 관건인 문제다. 이 아이디어를 잘 이해하고 다음에 잘 활용하자.

케이스1 설명

케이스3 설명

---

🎈 왜 이 문제에서는 graph 간선을 이중 for문으로 처리할까 ?

사실 처음에는 등수가 1~N등이 주어졌다면,
 이 관계가 1등→2등→3등→4등→5등 한쪽 열로만 쭉 이어졌으니 (4개의 방향 간선이 존재한다고) 생각했다.

 하지만, 이 문제는 간선 정보를 이중 for문으로
각 정점에 대해 자신보다 작은 등수의 정점들 정보를 모조리 다 연결해야 하는 문제다. 왜일까 ?

→ 이를 설명하기 위해서는 ‘위상정렬’의 위상 뜻이 뭔지부터 차근차근 접근해보자.
     위상 : 어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태 (즉, 상대적인 관계성)
     위상 정렬 : 상대적인 관계성 활용하여 정렬하라

그렇다. 사실 지금까지 풀었던 위상 정렬 문제들은 M번의 ‘상대적인 관계성’ 정보만 주어졌다.

 이를테면,  a가 b보다 키가 크다는 정보 1개로 우리가 할 수 있는 일은 a→ b 로의 1개 방향 간선밖에 추가할 수가 없었다.
그런데, 이 문제가 이중 for 문을 도는 것은 1등~N등까지의 정보가 주는 상대적 관계성 정보가 사실상은 여러 개의 정보이기 때문이다.

지금까지 많이 풀었던 위상 정렬 문제에서 주어진 ‘상대적 관계성’ 간선 정보의 경우는 다음과 같다.
단편적으로 A보다 B는 키가 크고요. C보다 E는 작은데, D보다 E는 커요!  즉, 이렇게 단편적인 정보로 주어진 상대적 관계성을 방향 graph에 간선으로 추가해서 위상 정렬을 수행했다.

그런데, 이 문제처럼 1등부터 5등까지의 정보가 주어진 경우는 총 10가지의 방향 간선 정보를 준 것으로 봐야 한다. 전체 관계를 관통하여 매길 수 있는 '등수' 정보는 상대적인 관계라기 보단 절대적인 정보이기 때문이다. 명확한 순서의 정렬 상태이므로.

따라서 문제가 제시한 각 정점의 등수 정보는 다음과 같은 방향 간선을 시사하는 말과 같다. 

    1등이 다른 4개의 정점보다 크다는 말이면서
    2등이 다른 3개의 정점보다 크다는 말이면서
    3등이 다른 2개의 정점보다 크다는 말이면서
    4등이 다른 1개의 정점보다 크다는 말이면서
    5등이 다른 0개의 정점보다 크다는 말이다.
그러니 각 정점을 기준으로 다른 등수에 대한 연결 정보를 이중 for문을 토대로 처리했던 것이다. 

---

🎈 ArrayList에 remove() 처리 시 주의할 점 | IndexOutOfBoundsException

IndexOutOfBoundsException 예외가 계속해서 발생했다. 

이는 ArrayList의 remove() 메소드 정의가 2개 있기 때문이다.

내가 호출하려고 헀던 메소드의 시그니처는 두 번째인데, int 형으로 remove()를 시도하니 첫 번째 메소드 시그니처를 호출했기 때문에 발생한 Exception이었다.

1) int remove(int idx)

// 지울 값의 인덱스 인자로 해당 값 지우고 지운 값을 int형으로 리턴

→ 이 메소드가 호출되면서 접근한 idx 범위가 실제 list 범위 넘어서서 Exception 터짐

2) boolean remove(Object obj)

// 지울 값의 obj를 인자로 줘서 해당 값이 list 상에 존재한다면 삭제 후 true리턴, 없다면 false 리턴

📌따라서 list에 접근해서 일부 값을 remove() 처리할 때는 주의해야 한다. 내 경우에는 int를 Wrapper 클래스인 Integer로 감싸서 Object 타입으로 형변환 시켜 자동으로 2번째의 메소드 시그니처 함수를 호출하도록 바꿨다. 이후 제대로 동작한다. 주의하자.

---

💚 제출 코드

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

/**
 * 3655번. 최종 순위 - 위상 정렬 문풀 
 * @author MYLG
 *
 */
public class Main {
	static int TC;
	static int N, M;
	static int[] rank;//작년 등수 
	static int[] indegree;
	static ArrayList<ArrayList<Integer>> graph;
	
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		TC = kb.nextInt();
		for(int t=0; t<TC; t++) {
			N = kb.nextInt();
			graph = new ArrayList<>();
			for(int i=0; i<=N; i++) {
				graph.add(new ArrayList<>());
			}
			
			rank = new int[N+1];
			indegree =new int[N+1];
			
			for(int i=1; i<=N; i++) rank[i]= kb.nextInt();
			
			for(int i=1; i<=N; i++) {
				for(int j=i+1; j<=N; j++) {
					//rank[i] -> rank[j] 방향 그래프
					graph.get(rank[i]).add(rank[j]);
					indegree[rank[j]]++;
				}
			}
			//등수 바뀐 m개
			M = kb.nextInt();
			
			for(int i=0; i<M; i++) {
				int a = kb.nextInt();
				int b = kb.nextInt();
				
				if(graph.get(a).contains(b)) {//기존 a-> b 방향이었으면 반전시킴
					graph.get(a).remove((Integer)b);
					graph.get(b).add(a);
					indegree[b]--;
					indegree[a]++;
				}else if(graph.get(b).contains(a)) { //기존 b-> a 방향이었으면 반전시킴
					graph.get(b).remove((Integer)a);
					graph.get(a).add(b);
					indegree[a]--;
					indegree[b]++;
				}
			}
			
			//위상정렬 시작
			Queue<Integer> Q = new LinkedList<>();
			for(int i=1; i<=N; i++) {
				if(indegree[i] == 0) {
					Q.offer(i);
				}
			}
			List<Integer> answer = new ArrayList<>();
			
			while(!Q.isEmpty()) {
				if(Q.size() > 1) {
					System.out.println("?");
					break;
				}
				int cur = Q.poll();
				answer.add(cur);
				for(int nx : graph.get(cur)) {
					indegree[nx]--;
					if(indegree[nx]==0) {
						Q.offer(nx);
					}
				}
			}
			
			if(answer.size() != N) {
				System.out.println("IMPOSSIBLE");
			}else {
				for(int x : answer) {
					System.out.print(x+" ");
				}
				System.out.println();
			}
		}
	}
}