[Java] 백준 12886 돌 그룹

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

난이도

골드4

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 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을 출력한다.

내 코드

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

public class Main {
    public static boolean[][] visited;
    public static int total;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        total = a + b + c;

        if (total % 3 != 0) {
            System.out.println(0);
            return;
        }

        visited = new boolean[total + 1][total + 1];
        System.out.println(bfs(a, b, c) ? 1 : 0);
    }

    public static boolean bfs(int a, int b, int c) {
        Queue<int[]> q = new LinkedList<>();
        int[] start = {a, b, c};
        Arrays.sort(start);

        q.offer(new int[]{start[0], start[1]});
        visited[start[0]][start[1]] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1], z = total - (x + y);

            if (x == y && y == z) return true;

            int[][] moves = {{x, y}, {x, z}, {y, z}};

            for (int[] m : moves) {
                if (m[0] != m[1]) {
                    int min = Math.min(m[0], m[1]);
                    int max = Math.max(m[0], m[1]);

                    int nx = min * 2;
                    int ny = max - min;
                    int nz = total - (nx + ny);

                    int[] sorted = {nx, ny, nz};
                    Arrays.sort(sorted);

                    if (!visited[sorted[0]][sorted[1]]) {
                        visited[sorted[0]][sorted[1]] = true;
                        q.offer(new int[]{sorted[0], sorted[1]});
                    }
                }
            }
        }
        return false;
    }
}

총 돌 개수가 3의 배수가 아니면 셋을 같은 숫자로 만들기가 불가능하기 때문에, (A + B + C) % 3 != 0 이면 3개의 돌을 같은 개수로 만들 수 없으므로 0을 출력하고 종료한다.

방문처리는 boolean[][] visited = new boolean[total+1][total+1]로 하고, (A, B, C) 중 가장 작은 두 개만 방문 배열로 관리를 한다. C는 total - (A + B)이므로 필요 없다.

현재 상태 (x, y, z)에서 돌 그룹을 (x, y), (x, z), (y, z) 세 가지 경우로 나눠 탐색한다. 작은 돌(min)을 두 배로 만들고, 큰 돌(max)에서 빼기 → (min * 2, max - min)를 수행하고, z = total - (nx + ny)로 나머지 값은 자동 계산이 된다.