백준 3665번 : 최종 순위 (Java)

 문제

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

3665번: 최종 순위

3665 최종 순위

 

 구현 방법

문제를 이해하는 데 시간이 넘나 오래 걸렸습니다.... 🤯

"예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다"

이 문장 때문에 너~~무 헷갈렸는데요.

아직도 정확하게 이해를 했는지.. 모르겠지만 일단 제가 이해한바로는 상대적인 순위가 더 높아질 수도, 더 낮아질 수도 있다 입니다.

 

따라서 이전 순위가 입력될 때 인접행렬을 이용하여 그래프를 표현하고

순위가 변동되면 인접행렬과 진입 차수를 변경해줍니다. (아래 그림 참고)

변경된 진입 차수와 인접행렬로 위상 정렬 알고리즘을 사용하여 구현할 수 있습니다.

 

확실한 순위를 알 수 없는 경우

진입 차수가 0으로 진입할 수 있는 정점의 개수가 1개여야 합니다.

만약 큐에 정점의 개수가 여러 개라면 이동할 수 있는 정점이 여러 개 ==  최종 순위가 여러 개 이므로

큐에는 한 번에 2개의 정점이 들어갈 수 없습니다.

데이터의 일관성이 없는 경우

변동된 순위로 사이클 형성 유무를 판단하게 되는데요

아직 순위를 다 결정하지 못했는데 큐가 비어있다면 사이클이 형성된 것으로 순위를 정할 수 없습니다.

 

 

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class B3665_최종순위 {
	static int TC, N, M, inDegree[];
	static boolean arr[][]; // 노드 관계를 저장할 인접행렬
	static Queue<Integer> queue;
	static StringBuilder ans = new StringBuilder(), sb;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		TC = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		while(TC-->0) {
			queue = new LinkedList<>();
			N = Integer.parseInt(br.readLine());
			inDegree = new int[N+1];
			arr = new boolean[N+1][N+1];
			st = new StringTokenizer(br.readLine());
			for (int i=0;i<N;i++) {
				int now = Integer.parseInt(st.nextToken());
				inDegree[now] = i; // 진입 차수는 등수대로
				for (int j=1;j<=N;j++) {
					// 관련 간선이 없다면 만들기
					if (j!=now && !arr[j][now]) arr[now][j] = true;
				}
			}
			
			M = Integer.parseInt(br.readLine());
			for (int i=0;i<M;i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				swap(from, to); // 순위 변경
			}
			
			ans.append(topology()+"\n");
		}
		System.out.println(ans);
	}
	
	static void swap(int from, int to) {
		// from->to가 false다 == from보다 to순위가 더 낮음 -> 높아져야됨
		if (!arr[from][to]) { 
			arr[from][to] = true;
			arr[to][from] = false;
			inDegree[from]--;
			inDegree[to]++;
		}
		// from->to가 true다 == from보다 to순위가 더 높음 -> 낮아져야됨
		else {
			arr[from][to] = false;
			arr[to][from] = true;
			inDegree[from]++;
			inDegree[to]--;
		}
	}
	
	static String topology() {
		sb = new StringBuilder();
		for (int i=1;i<=N;i++) {
			if (inDegree[i] == 0) queue.add(i);
		}
		
		for (int i=1;i<=N;i++) {
			// 사이클 발생 IMPOSSIBLE
			if (queue.isEmpty()) return "IMPOSSIBLE"; 
			// 이동할 수 있는 정점이 여러 개 == 나올 수 있는 최종 순위가 여러 개
			else if (queue.size()>1) return "?"; 
			
			int now = queue.poll();
			sb.append(now+" ");
			
			for (int j=1;j<=N;j++) { 
				if (arr[now][j]) { // 이동할 수 있는 정점 
					arr[now][j] = false; // 이동했다!
					// 진입 차수 줄여주고 0이면 이동
					if (--inDegree[j] == 0) queue.add(j); 
				}
			}
		}
		return sb.toString();
	}
}

 

정답!