BOJ#3665 최종 순위

BOJ#3665 최종 순위

* 문제

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

* 풀이

위상 정렬 문제입니다.

- 위상 정렬 설명  : http://terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093

첫 예제를 통해 어떻게 문제를 풀지 생각해보겠습니다.

5 4 3 2 1

1. 간선과 indegree를 아래와 같이 추가합니다. 

간선의 경우 인접리스트보다는 인접행렬로 구현하는게 더 효율적일 것 같습니다.

<간선>

5->4, 5->3, 5->2, 5->1

4->3, 4->2, 4->1

3->2, 3->1

2->1

<indegree>

[0, 4, 3, 2, 1, 0]

int[][] graph = new int[n + 1][n + 1];

// n^2 으로 인접행렬 생성, indegree 생성
for (int i = 0; i < n; i++) {

    for (int j = i + 1; j < n; j++) {

        graph[t[i]][t[j]] = 1;
        indegree[t[j]]++;
    }
}

2. 바뀐 순위에 따라 간선과 indgree를 갱신해줍니다.

2 4

3 4

주의할점으로는 

2가 4보다 우선순위가 높다는 뜻이 아니라 2와 4가 서로 우선 순위가 뒤바뀌었다는 뜻입니다.

따라서 indegree배열은 아래와 같이 변경될 것입니다.

[0, 4, 3, 2, 1, 0] -> [0, 4, 2, 1, 3, 0]

[0, 3, 1, 0, 2, 0]

[0, 2, 0, 0, 1, 0]

[0, 1, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

// 바뀐 순위의 개수 m
int m = Integer.parseInt(br.readLine());

// 바뀐 순위에 따라 간선과 indegree를 갱신한다
for (int i = 0; i < m; i++) {

    st = new StringTokenizer(br.readLine());

    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());


    if (graph[a][b] == 1) {

        graph[a][b] = 0;
        graph[b][a] = 1;

        indegree[a]++;
        indegree[b]--;
    } else {

        graph[b][a] = 0;
        graph[a][b] = 1;

        indegree[a]--;
        indegree[b]++;
    }
}

3. 위상 정렬을 합니다.

indegree가 0인 노드를 queue에 넣는다

 -> queue에서 노드를 하나 꺼낸다

 -> 꺼낸 노드의 인접 노드들의 indegree를 하나씩 빼준다

 -> indegree가 0인 노드를 queue에 넣는다

indegree 변화는 아래와 같을 것입니다.

[0, 4, 2, 1, 3, 0]

[0, 3, 1, 0, 2, 0]

[0, 2, 0, 0, 1, 0]

[0, 1, 0, 0, 0, 0]

[0, 0, 0, 0, 0, 0]

,

위상 정렬에서는 loop를 한번 돌때마다 노드가 한개씩 처리되므로

n번의 loop를 돌아야 합니다.

그런데 여기서 사이클이 생긴다면 n번 loop가 다 돌기 전에 queue가 비어버리는 상황이 발생할 것입니다. (즉, indegree가 0이 되지 않는 상황)

이 경우에는 IMPOSSIBLE을 출력하면 됩니다.

☞ TestCase

E.in

E.out

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/1d6df17ad9012986242de8c108faa7adc14e1f32/BOJ%233665_Rankings/src/Main.java

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * BOJ#3665 Rankings 최종 순위
 * https://www.acmicpc.net/problem/3665
 */

public class Main {

    static final int NONE = 0;
    static final int IMPOSSIBLE = 1;
    static final int NOT_DETERMINED = 2;

    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 입력
            int n = Integer.parseInt(br.readLine());

            // indegree배열과 인접행렬 생성
            int[] indegree = new int[n + 1];
            int[][] graph = new int[n + 1][n + 1];

            int[] t = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {

                t[i] = Integer.parseInt(st.nextToken());
            }

            // n^2 으로 인접행렬 생성, indegree 생성
            for (int i = 0; i < n; i++) {

                for (int j = i + 1; j < n; j++) {

                    graph[t[i]][t[j]] = 1;
                    indegree[t[j]]++;
                }
            }

            // 바뀐 순위의 개수 m
            int m = Integer.parseInt(br.readLine());

            // 바뀐 순위에 따라 간선과 indegree를 갱신한다
            for (int i = 0; i < m; i++) {

                st = new StringTokenizer(br.readLine());

                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());


                if (graph[a][b] == 1) {

                    graph[a][b] = 0;
                    graph[b][a] = 1;

                    indegree[a]++;
                    indegree[b]--;
                } else {

                    graph[b][a] = 0;
                    graph[a][b] = 1;

                    indegree[a]--;
                    indegree[b]++;
                }
            }

            // 위상정렬
            // queue에 2개 이상 입력된다면 순위를 정할 수 없다. -> ? 출력
            // loop가 n번 돌기 전에 queue가 비워진다면 사이클이 생긴 것이므로 IMPOSSIBLE -> 노드는 남아있는데 indegree가 0인 노드가 없는 상태

            Queue<Integer> queue = new LinkedList<>();
            int[] rankings = new int[n];

            for (int i = 1; i <= n; i++) {

                if (indegree[i] == 0) {

                    queue.add(i);
                }
            }

            int ans = NONE;
            for (int i = 0; i < n; i++) {

                if (queue.isEmpty()) {

                    ans = IMPOSSIBLE;
                    break;
                }

                if (queue.size() > 1) {

                    ans = NOT_DETERMINED;
                    break;
                }

                int u = queue.poll();
                rankings[i] = u;

                for (int j = 1; j < n + 1; j++) {

                    if (graph[u][j] == 1) {

                        indegree[j]--;

                        if (indegree[j] == 0) queue.add(j);
                    }
                }
            }

            if (ans == NONE) {

                for (int x : rankings) bw.write(x + " ");
                bw.write("\n");
            } else if (ans == IMPOSSIBLE) bw.write("IMPOSSIBLE\n");
            else if (ans == NOT_DETERMINED) bw.write("?\n");

        } // ~test case loop

        bw.flush();

        bw.close();
        br.close();
    }
}