[Gold IV] 돌 그룹 - 12886

문제 링크

성능 요약

메모리: 69936 KB, 시간: 260 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 3월 14일 15:33:01

문제 설명

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

문제 풀이

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_12886_돌그룹/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        boolean isAble = bfs(A, B, C);
        System.out.println(isAble ? "1" : "0");
        bw.flush();
        bw.close();
        br.close();
    }

    private boolean bfs(int A, int B, int C) {
        int totalW = A + B + C;
        if (totalW % 3 != 0) return false;
        if (A == B && B == C) return true;

        int[] arr = new int[]{A, B, C};
        Arrays.sort(arr);

        boolean[][] visited = new boolean[totalW + 1][totalW + 1];
        Queue<int[]> queue = new LinkedList<>();
        visited[arr[0]][arr[1]] = true;
        queue.offer(new int[]{arr[0], arr[1], arr[2]});

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int a = curr[0];
            int b = curr[1];
            int c = curr[2];

            List<int[]> list = new ArrayList<>();
            list.add(new int[]{a, b, totalW - a - b});
            list.add(new int[]{b, c, totalW - b - c});
            list.add(new int[]{c, a, totalW - c - a});

            for (int[] l : list) {
                int x = l[0];
                int y = l[1];
                if (x == y) continue;

                int nx, ny;
                if (x < y) {
                    nx = x + x;
                    ny = y - x;
                } else {
                    nx = x - y;
                    ny = y + y;
                }

                int next[] = {nx, ny, totalW - nx - ny};
                Arrays.sort(next);
                if (!visited[next[0]][next[1]]) {
                    if (next[0] == next[1] && next[1] == next[2]) return true;

                    visited[next[0]][next[1]] = true;
                    queue.offer(new int[]{next[0], next[1], next[2]});
                }
            }
        }
        return false;
    }
}