[BOJ 3665] 최종 순위 (Java)

BOJ 3665 최종 순위

난이도 : 골드 1

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

3665번: 최종 순위

 

전략

1. 각 팀의 기존 순위를 그래프로 표현

2. 변경된 순위로 간선의 방향을 반대로 변경

3. 위상 정렬을 통해 최종 순위 출력

 

시행착오

처음에는 위처럼 일방향으로 그래프를 이어줬는데 위 상태에서는 순위 변경에 따라 간선 방향을 변경할 수 없다.

 

따라서 자신보다 뒷 순위 팀을 모두 가리키도록 그래프를 구성하고, 변경된 순서에 따라 간선 방향을 변경하면 된다.

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T, N, M;
        T = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine());
            Node[] nodes = new Node[N + 1];
            for (int i = 1; i <= N; i++)
                nodes[i] = new Node(i);

            String[] line = br.readLine().split(" ");
            ArrayList<Node> temp = new ArrayList<>();
            // nodes init
            for (int i = N - 1; i >= 0; i--) {
                int num = Integer.parseInt(line[i]);
                nodes[num].link.addAll(temp);
                nodes[num].linked = N - (temp.size() + 1);
                temp.add(nodes[num]);
            }

            M = Integer.parseInt(br.readLine());
            for (int i = 0; i < M; i++) {
                line = br.readLine().split(" ");
                int first = Integer.parseInt(line[0]);
                int second = Integer.parseInt(line[1]);
                if (nodes[first].link.contains(nodes[second])) {
                    nodes[first].link.remove(nodes[second]);
                    nodes[second].linked--;
                    nodes[second].link.add(nodes[first]);
                    nodes[first].linked++;
                } else {
                    nodes[second].link.remove(nodes[first]);
                    nodes[first].linked--;
                    nodes[first].link.add(nodes[second]);
                    nodes[second].linked++;
                }
            }
            System.out.println(topologySort(nodes, N));
        }
        br.close();
    }

    static StringBuilder topologySort(final Node[] nodes, int N) {
        StringBuilder sb = new StringBuilder();
        Queue<Node> queue = new LinkedList<>();

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

        for (int i = 0; i < N; i++) {
            if (queue.isEmpty())
                return new StringBuilder("IMPOSSIBLE");
            if (queue.size() > 1)
                return new StringBuilder("?");

            Node cur = queue.poll();
            sb.append(cur.num + " ");

            for (Node next : cur.link) {
                if (--next.linked == 0)
                    queue.offer(next);
            }
        }

        return sb;
    }

    static class Node {
        int num;
        int linked = 0;
        ArrayList<Node> link = new ArrayList<>();
        Node(int num) {
            this.num = num;
        }
    }
}

 

깨달은 점

위상 정렬을 이용한 문제였는데, 일상생활에서 나타날 수 있는 상황을 그래프로 표현하고 해결하는 것이 흥미롭다.