[백준] 12886. 돌 그룹

문제 링크

[백준] 12886. 돌 그룹

풀이 과정

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

위 규칙을 따르면, X 그룹의 돌 개수는 X+X개로 바뀌고, Y그룹의 돌 개수는 Y-X로 바뀝니다. 이는 Y 그룹에서 X 그룹의 돌 개수만큼을 X그룹으로 옮기는 동작입니다. 즉, 세 그룹의 돌 개수 총합은 처음과 바뀌지 않습니다.

이제 돌을 옮기는 부분을 생각해봅시다.

위 예시에서, 기존 배열 [10, 15, 35] 중 X와 Y를 각각 10과 15로 설정합니다. 재배치된 배열 [20, 5, 35] 에서 X와 Y를 각각 5와 20으로 설정하면, 재배치된 결과로 원래 배열이 등장하게 됩니다. 이런 식으로 모든 경우를 탐색하려고 하면 호출 스택에 재귀 함수가 무한정 쌓이는 현상이 발생합니다.

따라서, 우리는 각 돌 그룹을 하나의 노드로 보고, 그래프 탐색 알고리즘을 적용할 필요가 있습니다. 한 번 방문했던, 즉 만들어졌던 돌 개수는 그 결과를 알기에 다시 탐색하지 않게 됩니다.

그렇다면, 방문 처리는 어떻게 해야 될까요? 우리는 세 그룹 A, B, C의 돌 개수를 지지고 볶아야 하기 때문에, 가장 먼저 이 세 숫자가 모두 사용되는 3차원 방문 처리 배열을 생각해볼 수 있습니다. 방문 처리 배열을 visit 이라고 하면, visit[A][B][C] = true 이면, X 그룹의 돌 개수를 A, Y 그룹의 돌 개수를 B, 나머지 그룹의 돌 개수를 C로 만들어 봤다 정도의 의미로 해석할 수 있게 됩니다.

위처럼 방문 처리 배열을 설정했을 때의 메모리는 어떻게 잡힐까요? 각 그룹의 돌 개수는 최대로 약 1500개까지 가능합니다. 각 그룹의 돌 개수가 500, 499, 498이라고 설정되면, 한쪽으로 돌 개수를 몰면 약 1500개로 위치할 수 있습니다. 즉, 3차원 방문 처리 배열은 1500X1500X1500 의 크기가 필요합니다. 이는 $1500*1500*1500B=3375*10^6B$ 의 메모리를 차지합니다. 메모리 제한 $512MB=512*10^6B$ 에 비해 훨신 큰 수라는 것을 알 수 있습니다. 따라서, 3차원 배열을 사용하게 되면 메모리 제한에 걸리게 됩니다.

결론을 말하면, 2차원 배열로 충분히 방문 처리를 할 수 있습니다. 두 그룹의 돌 개수(A, B)를 알고 있으면 나머지 그룹의 돌 개수(sum - A - B)는 자동으로 주어지기 때문입니다.

for (int cnt : stones) sum += cnt;

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

먼저 각 그룹의 돌 개수를 다 sum에 누적시킵니다. sum 이 3으로 딱 나눠떨어지지 않으면, 세 그룹이 동일한 돌 개수를 갖지 못하므로 0을 출력한 뒤 프로그램을 종료시킵니다.

Queue<int[]> q = new LinkedList<>();
visit[stones[0]][stones[1]] = true;
q.add(new int[]{stones[0], stones[1], stones[2]});

while (!q.isEmpty()) {
    int[] now = q.poll();

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (now[i] < now[j]) {
                int nx = now[i] + now[i];
                int ny = now[j] - now[i];

                if (visit[nx][ny]) continue;

                visit[nx][ny] = true;
                q.add(new int[]{nx, ny, sum - nx - ny});
            }
        }
    }
}

초기 문제에서 주어진 개수 A, B, C 를 방문 체크한 후, 큐에 담고 BFS 탐색을 진행합니다. 가능한 6가지 경우를 조사하며, 바뀐 돌 개수가 처음 등장한다면, 방문 처리 후 큐에 담고 탐색을 계속합니다.

System.out.println(visit[sum / 3][sum / 3] ? 1 : 0);

출력은 방문처리의 좌표 ($\frac{sum}{3}$, $\frac{sum}{3}$)의 요소 값에 결정됩니다. 좌표 ($\frac{sum}{3}$, $\frac{sum}{3}$)에 방문했다는 것은, 모든 돌 그룹의 개수를 $\frac{sum}{3}$개로 같도록 재배치한 적이 있다는 의미가 됩니다.

코드

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

public class Main {
    static int[] stones;
    static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stones = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        visit = new boolean[1501][1501];
        int sum = 0;
        for (int cnt : stones) sum += cnt;

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

        Queue<int[]> q = new LinkedList<>();
        visit[stones[0]][stones[1]] = true;
        q.add(new int[]{stones[0], stones[1], stones[2]});

        while (!q.isEmpty()) {
            int[] now = q.poll();

            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (now[i] < now[j]) {
                        int nx = now[i] + now[i];
                        int ny = now[j] - now[i];

                        if (visit[nx][ny]) continue;

                        visit[nx][ny] = true;
                        q.add(new int[]{nx, ny, sum - nx - ny});
                    }
                }
            }
        }

        System.out.println(visit[sum / 3][sum / 3] ? 1 : 0);
    }
}