백준 : 3665 (위상정렬)

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

3665번: 최종 순위

 

깔끔한 풀이가 안떠올라서 생각나는 데로 풀었다.

 

만약 어떤 팀의 우승 순서가 이어진다면 노드로 이어보면

5 <- 4<- 3<- 2<- 1 형태의 그래프를 이을 수 있다.

 

이것을 위상그래프로 생각해본다면

5<-4, 5<-3, 5<-2, 5<-1

4<-3, 4<-2, 4<-1

3<-2, 3<-1

2<-1 

 

그래프가 그려지는 것을 알 수 있고 바꾸는 두 정점에대하여 바꾼뒤 들어오는 차수와 나가는 차수를 이용해서 위상정렬을 할 수 있다.

 

문제에서는 여러 케이스가 아닌 오직 하나의 위상정렬만 되는 case에 대해서만 정답을 출력하니

Parrent 차수 + childe차수 == N-1 을 유지하는 위상정렬 중에 rank가 옳바르게 뽑힌 녀석들만 출력하면 된다.

 

이렇게하면 정답은 나오지만 깔끔한 풀이가 아닌것 같아서 다른 블로그를 보고 참조해보겠다.

내가 푼 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.StringTokenizer;

public class B3665 {
	static int Tc;
	static int N, M;
	static int seq[];
	static ArrayList<Integer> Vex[];
	static int parrent[];
	static int child[];
	static int rank[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		Tc = Integer.parseInt(br.readLine());

		while (Tc-- != 0) {
			N = Integer.parseInt(br.readLine());
			seq = new int[N];
			st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++)
				seq[n] = Integer.parseInt(st.nextToken());

			Vex = new ArrayList[N + 1];
			for (int n = 1; n <= N; n++)
				Vex[n] = new ArrayList<>();

			for (int i = 0; i < N - 1; i++) {
				for (int j = i + 1; j < N; j++) {
					Vex[seq[j]].add(seq[i]);
				}
			}

			M = Integer.parseInt(br.readLine());
			for (int m = 0; m < M; m++) {
				st = new StringTokenizer(br.readLine());
				// a <- b
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				// b <- a 엿던것을 a < - b로 바꾼다.

				// b <- a edge 제거
				boolean isChange = false;
				for (Iterator<Integer> it = Vex[a].iterator(); it.hasNext();) {
					int cur = it.next();
					if (cur == b) {
						it.remove();
						isChange = true;
						break;
					}
				}

				if (isChange) {
					// a<-b 엣지 추가
					Vex[b].add(a);
				} else {
					for (Iterator<Integer> it = Vex[b].iterator(); it.hasNext();) {
						int cur = it.next();
						if (cur == a) {
							it.remove();
							break;
						}
					}
					Vex[a].add(b);
				}
			}

			// 연결이 끝나면 위상을 확인하는데 parrent child 수라 확인한다.
			parrent = new int[N + 1];
			child = new int[N + 1];
			rank = new int[N + 1];

			// parrent + child 의 합은 항상 N-1 이어야한다.

			for (int n = 1; n <= N; n++) {
				for (int next : Vex[n]) {
					// next <- n 노드이다.
					parrent[n]++;
					child[next]++;
				}
			}

			boolean isPossible = false;

			// rank를 구한다.
			for (int n = 1; n <= N; n++) {
				if ((parrent[n] + child[n]) != N - 1) {
					isPossible = true;
					break;
				}
				rank[parrent[n] + 1] = n;
			}

			for (int n = 1; n <= N; n++) {
				if (rank[n] == 0) {
					isPossible = true;
					break;
				}
			}

			if (isPossible) {
				sb.append("IMPOSSIBLE\n");
			} else {
				for (int n = 1; n <= N; n++) {
					sb.append(rank[n]).append(' ');
				}
				sb.append('\n');
			}

		}
		System.out.println(sb.toString());
	}
}

 

다른사람 방법

입력과 위상이 바뀌는 정보 까지는 똑같다.

1. inDegree가 0인 애들을 기준으로 q에다가 저장한다.

2. q에서 뺏을 때 q 사이즈가 0이 아닌경우에는 현재 inDegree가 0인 애들이 동시에 존재한다는거니 impossible을 반환한다.

3. q 사이즈가 0이 아닌경우에는 pop된 node를 기준으로 연결된 그래프들의 inDegree를 --한다.
이때 inDegree가 0이 되는 애들을 q에 push한다.

위의 과정을 반복할때 inDegree가 0이 되는 순서가 순서의 역순이 된다.