[백준] 3665 최종 순위 - 자바

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

3665번: 최종 순위

문제 풀이

위상 정렬로 순위를 관리하는 문제이다. 순위가 5 4 3 2 1로 주어졌다면, 순위가 높은 노드 -> 낮은 노드로 유향 간선을 그려 진입차수를 고려해보자. 그럼 5 4 3 2 1 순서대로 진입차수는 0 1 2 3 4이 될 것이다. 

 

그렇다면 위처럼 진입차수가 중복없이 순차적이지 않고 중복이 생겨 0 1 1 2 3이면 무슨 일이 생길까?

진입차수가 0이라는 것은 자기 자신보다 높은 순위의 노드는 없다는 뜻이다. 그럼 1이 두 개로 중복이라는 뜻은 같은 순위라는 뜻이다.

즉, 순위를 알 수 없다. 따라서 '?'를 출력한다.

 

위 로직에 맞게 코딩을 해보자.

먼저 자식노드와 진입 차수를 관리하는 코드이다.

static int inDegree[];
static boolean children[][]; // children[i][j]=true : i는 j의 부모 노드

N = Integer.parseInt(br.readLine());

inDegree = new int[N + 1];
children = 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 && !children[j][now]) children[now][j] = true;
    }
}

 

다음으로 변경된 순위에 대해 swap 하는 함수이다.

static void swap(int from, int to) {
    // [from][to]=false : from보다 to순위가 더 낮음 -> from은 높게, to는 낮게 swap
    if (!children[from][to]) {
        children[from][to] = true;
        children[to][from] = false;
        inDegree[from]--;
        inDegree[to]++;
    }
    // [from][to]=true : from보다 to순위가 더 높음 -> from은 낮게, to는 높게 swap
    else {
        children[from][to] = false;
        children[to][from] = true;
        inDegree[from]++;
        inDegree[to]--;
    }
}

 

마지막으로 위상 정렬을 수행하며 조건에 맞는 리턴값을 반환한다.

static String topology() {
    StringBuilder sb = new StringBuilder();
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            queue.add(i);
        }
    }

    for (int i = 1; i <= N; i++) {
        // 진입차수가 0인 노드가 없어서 q가 비어있다면 -> 사이클 발생 -> 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 (children[now][j]) { // 이동할 수 있는 정점
                children[now][j] = false; // 이동했다!
                // 이동 했으니 진입차수 감소
                inDegree[j]--;
                if (inDegree[j] == 0) {
                    queue.add(j);
                }
            }
        }
    }
    return sb.toString();
}

 

코드

package 백준;

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 N, M, inDegree[];
    static boolean children[][]; // children[i][j]=true : i는 j의 부모 노드
    static Queue<Integer> queue;
    static StringBuilder ans = new StringBuilder();
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        StringTokenizer st;

        while(testCase-->0) {
            queue = new LinkedList<>();
            N = Integer.parseInt(br.readLine());

            inDegree = new int[N + 1];
            children = 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 && !children[j][now]) children[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순위가 더 낮음 -> from은 높게, to는 낮게 swap
        if (!children[from][to]) {
            children[from][to] = true;
            children[to][from] = false;
            inDegree[from]--;
            inDegree[to]++;
        }
        // [from][to]=true : from보다 to순위가 더 높음 -> from은 낮게, to는 높게 swap
        else {
            children[from][to] = false;
            children[to][from] = true;
            inDegree[from]++;
            inDegree[to]--;
        }
    }

    static String topology() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        for (int i = 1; i <= N; i++) {
            // 진입차수가 0인 노드가 없어서 q가 비어있다면 -> 사이클 발생 -> 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 (children[now][j]) { // 이동할 수 있는 정점
                    children[now][j] = false; // 이동했다!
                    // 이동 했으니 진입차수 감소
                    inDegree[j]--;
                    if (inDegree[j] == 0) {
                        queue.add(j);
                    }
                }
            }
        }
        return sb.toString();
    }
}