[SWEA] 10993 군주제와 공화제 (Java)

1.  문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AXXfloFa29EDFAST&categoryId=AXXfloFa29EDFAST&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=17

2.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Solution {
    static final Map<Integer, Character> CONSTANT = new HashMap<Integer, Character>() {{
        put(-1, 'K');
        put(-2, 'D');
    }};

    static StringBuilder answer = new StringBuilder();
    static Reader scanner = new Reader();

    static int cityCount;
    static double[][] influence;
    static int[] parents;
    static List<City> cities;
    static List<Integer>[] dominantCities;

    static void input() {
        cityCount = scanner.nextInt();
        influence = new double[cityCount][cityCount];
        parents = new int[cityCount];
        cities = new ArrayList<>();
        dominantCities = new ArrayList[cityCount];
        Arrays.fill(parents, Integer.MIN_VALUE);

        for (int idx = 0; idx < cityCount; idx++) {
            cities.add(new City(scanner.nextInt(), scanner.nextInt(), scanner.nextInt()));
            dominantCities[idx] = new ArrayList<>();
        }
    }

    static void solution() {
        calculateInfluence();
        findDominantCities();
        print();
    }

    static void print() {
        IntStream.range(0, cityCount).forEach(parent -> {
            int followingCity = findFollowingCity(parent);
            if (CONSTANT.containsKey(followingCity)) {
                answer.append(CONSTANT.get(followingCity)).append(' ');
                return;
            }

            answer.append(followingCity + 1).append(' ');
        });
        answer.append('\n');
    }

    static int findFollowingCity(int idx) {
        if (parents[idx] == -1 || parents[idx] == -2) {
            return parents[idx];
        }
        return findParent(idx);
    }

    static int findParent(int city) {
        if (parents[city] == -1 || parents[city] == -2) {
            return city;
        }
        return parents[city] = findParent(parents[city]);
    }

    static void calculateInfluence() {
        for (int basis = 0; basis < cityCount; basis++) {
            for (int other = 0; other < cityCount; other++) {
                if (basis == other) {
                    continue;
                }

                City basisCity = cities.get(basis);
                City otherCity = cities.get(other);
                double distanceSquare = calculateDistanceSquare(basisCity, otherCity);
                influence[basis][other] = basisCity.militaryPower / distanceSquare;
            }
        }
    }

    static double calculateDistanceSquare(City city1, City city2) {
        return Math.pow(city2.x - city1.x, 2) + Math.pow(city2.y - city1.y, 2);
    }

    static void findDominantCities() {
        for (int basis = 0; basis < cityCount; basis++) {
            for (int other = 0; other < cityCount; other++) {
                if (basis == other) {
                    continue;
                }

                if (influence[other][basis] > cities.get(basis).militaryPower) {
                    dominantCities[basis].add(other);
                }
            }

            sort(basis, dominantCities[basis]);
            findCityInfo(basis);
        }
    }

    static void sort(int basisCity, List<Integer> dominantCities) {
        Collections.sort(dominantCities, (cityIdx1, cityIdx2) -> {
            if (influence[cityIdx1][basisCity] < influence[cityIdx2][basisCity]) {
                return 1;
            }
            if (influence[cityIdx1][basisCity] > influence[cityIdx2][basisCity]) {
                return -1;
            }
            return 0;
        });
    }

    static void findCityInfo(int basisIdx) {
        if (dominantCities[basisIdx].size() == 0) {
            parents[basisIdx] = -1;
            return;
        }

        if (dominantCities[basisIdx].size() == 1) {
            parents[basisIdx] = dominantCities[basisIdx].get(0);
            return;
        }

        List<Integer> dominantCity = dominantCities[basisIdx];
        double max = influence[dominantCity.get(0)][basisIdx];
        if (max == influence[dominantCity.get(1)][basisIdx]) {
            parents[basisIdx] = -2;
            return;
        }
        parents[basisIdx] = dominantCities[basisIdx].get(0);
    }

    static class City {
        int x;
        int y;
        int militaryPower;

        public City(int x, int y, int militaryPower) {
            this.x = x;
            this.y = y;
            this.militaryPower = militaryPower;
        }
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();
        for (int test = 1; test <= T; test++) {
            answer.append('#').append(test).append(' ');
            input();
            solution();
        }
        System.out.print(answer);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

3.  접근

• 각 도시가 다른 모든 도시에 행사하는 영향력을 구하여 이를 influence라는 2차원 배열에 저장한다.
  • influence[city1][city2] = city1이 city2에 행사하는 영향력
• 각 도시를 위협하고 있는 다른 도시들을 구하여 이를 dominantCities라는 List 배열에 저장한다.
  • 이때 List에는 각 도시를 위협하고 있는 도시의 번호가 들어가는데, 이는 위협하고 있는 도시가 위협받고 있는 도시에게 행사하는 영향력 기준 내림차순으로 정렬되어있다.
• 만약 List에 아무 값도 들어있지 않다면 이는 해당 도시를 위협하고 있는 도시가 없다는 뜻이 되기 때문에 해당 도시는 군주제가 된다.
• 만약 List에 값이 하나만 들어있다면 위협하고 있는 도시가 유일하다는 뜻이므로 영향력이 가장 큰 도시가 유일한 상황이기 때문에 위협하고 있는 도시의 번호를 parents라는 배열에 저장해놓는다.
• 만약 List에 값이 둘 이상인데 가장 앞의 도시와 그 바로 뒤의 도시의 영향력이 같다면 영향력이 가장 큰 도시가 두 개 이상이므로 공화제가 된다.
• 위 세 가지 경우에 모두 속하지 않는다면 parents라는 배열에 가장 위협하고 있는 도시의 번호를 저장해놓는다.
• parents 배열에는 각 도시가 군주제라면 -1, 공화제라면 -2, 둘 다 아니라면 가장 위협하고 있는 도시의 번호가 저장되어 있을 것이다.
• 이제 union find를 이용하여 군주제나 공화제가 된 도시까지 가장 위협하고 있는 도시를 타고 올라가면서 체제를 따르는 도시를 구한다.