Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

35. 위상 정렬

간선에 방향이 있는 그래프의 정점을 나열해 역방향이 없게 만드는 알고리즘을 다뤄 봅시다.

2. 최종 순위

3665번

간선을 직접 정의한 다음 위상정렬을 하는 문제

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

위상정렬은 보통 A가 B보다 앞에 있는 경우인데, 이런 경우 단순하게 하나씩 관계를 보면 된다. 그런데 이번 문제는 순서가 미리 정해져 있으며, 순위의 앞뒤관계가 바뀌는 경우라 조금 더 복잡한 형태의 위상 정렬 문제라고 볼 수 있다. 따라서 이번 문제의 경우 순위에 따라, 모든 관계를 추가한다.

바뀐 순위들에 대해서 edge의 방향을 바꾸고 위상 정렬을 시행한다. 같은 진입 차수에 있어 순서를 구분할 수 없는 경우에는 "?"를, 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 (주어지는 정보에서 사이클이 발생하는 경우)에는 "IMPOSSIBLE"을 출력한다.

Java / Python

• Java

import java.io.*;
import java.util.*;

public 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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());

		while (T-- > 0) {
			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);
			}
			bw.write(topologicalSort() + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	private static String topologicalSort() {
		Queue<Integer> queue = new LinkedList<>();
		StringBuilder sb = new StringBuilder();

		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0)
				queue.offer(i);
		}

		for (int i = 1; i <= N; i++) { // 정점 개수만큼 반복
			if (queue.size() == 0)
				return "IMPOSSIBLE";
			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] = false;
			edges[n2][n1] = true;
			indegree[n1]++;
			indegree[n2]--;

		} else {
			edges[n1][n2] = true;
			edges[n2][n1] = false;
			indegree[n1]--;
			indegree[n2]++;
		}
	}
}

• Python

import sys
from collections import deque

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    rank = list(map(int, sys.stdin.readline().split()))
    edges = [[False]*(n+1) for _ in range(n + 1)]
    indegree = [0] * (n + 1)
    
    for i in range(n):
        for j in range(i + 1, n):
            edges[rank[i]][rank[j]] = True
            
    m = int(sys.stdin.readline())
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        edges[a][b], edges[b][a] = edges[b][a], edges[a][b]

    que = deque()
    answer = []
    cnt = 0
    for i in range(1, n + 1):
        indegree[i] = edges[i].count(True)
        if indegree[i] == 0:
            cnt += 1
            que.append(i)

    if cnt != 1:
        if cnt > 1:
            print("?")
        elif cnt == 0:
            print("IMPOSSIBLE")
        continue
            
    while que and cnt == 1:
        cnt = 0
        cur = que.popleft()
        answer.append(cur)
        for i in range(1, n + 1):
            if edges[i][cur]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    cnt += 1
                    que.append(i)
                    
    if cnt > 1:
        print("?")
    elif len(answer) != n:
        print("IMPOSSIBLE")
    else:
        print(*answer[::-1])