[랜덤 마라톤] CTP 왕국은 한솔 왕국을 이길 수 있을까?(15789)

1. 문제 풀이 아이디어

• BFS를 사용하여 각 왕국의 힘을 계산하고, 해당 힘을 조건에 따라 저장한 뒤 최종 결과를 계산한다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n = Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        List<List<Integer>> list = new ArrayList<>();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int x = Integer.parseInt(stringTokenizer.nextToken()) - 1;
            int y = Integer.parseInt(stringTokenizer.nextToken()) - 1;
            list.get(x).add(y);
            list.get(y).add(x);
        }
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int c = Integer.parseInt(stringTokenizer.nextToken()) - 1;
        int h = Integer.parseInt(stringTokenizer.nextToken()) - 1;
        int k = Integer.parseInt(stringTokenizer.nextToken());
        int result = 1;
        PriorityQueue<Integer> powerQueue = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(i);
            int chk = 0;
            int power = 0;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                power++;
                if (cur == c)
                    chk = 1;
                if (cur == h)
                    chk = 2;
                for (int j : list.get(cur)) {
                    if (visited[j]) continue;
                    visited[j] = true;
                    queue.add(j);
                }
            }
            if (chk == 0)
                powerQueue.add(power);
            if (chk == 1)
                result = power;
        }
        for (int i = 0; i < k && !powerQueue.isEmpty(); i++) {
            result += powerQueue.poll();
        }
        System.out.println(result);
        bufferedReader.close();
    }
}

3. 정리

• List를 사용해 입력 데이터를 그래프로 구성한다.

• BFS를 통해 각 왕국의 힘을 계산한다.

• 왕국에 c가 포함되어 있다면 result에 해당 힘을 저장한다.

• 왕국에 h가 포함되어 있다면 해당 왕국은 무시한다.

• 두 노드 모두 포함하지 않는 왕국의 힘은 PriorityQueue에 저장한다.

• k번 반복하여 PriorityQueue에서 가장 큰 값을 꺼내 result에 더한다.

• 최종적으로 result를 출력하여 문제를 해결한다.