[BOJ12886] 돌 그룹

문제 설명

문제 링크

• A, B, C 숫자 세개가 입력으로 주어진다.
• 세 개의 숫자 중, 크기가 다른 두 개를 선택한다.(작은 수를 X, 큰 수를 Y)
• X는 X+X로, Y는 Y-X로 만든다.
• 이렇게 반복했을 때, 세개의 돌을 모두 같은 수로 만들 수 있는지 없는지를 판단하는 문제이다.

생각의 흐름

• 완전탐색으로 풀 수 있다는 생각을 처음에 하지 못하고, 수학적인 방법이 있을거라고 생각하고 접근했다.
• 하지만 풀이를 생각하다 보니, A,B,C는 변형이 일어나도 늘 합이 같고, 가지 수가 생각보다 늘어나지 않는다는 것을 알게 되었다.
• A, B, C에서 2개를 골라 A’, B’로 변형을 시키고, C는 sum - (A’ + B’)로 구할 수 있었다.
• 이렇게 세개의 숫자를 visit에 저장해서(실제 저장할 땐 3개를 다 저장하진 않는다.) 방문 체크를 해주었고, 모든 경우의 탐색이 끝났을 때 세 숫자의 합이 동일한 경우가 없었다면 false를 리턴해준다.

풀이

• bfs를 도는 큐에 a,b,c를 담고있는 노드를 저장하고, 처음 세개의 숫자의 합을 저장해둔다.

int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
sum = a + b + c;
q.add(new Node(a, b, c));

• 큐에서 뺀 노드를 통해, 순차적으로 다음에 나타날 수 있는 숫자들을 파악한다.
• a,b,c 세개의 숫자 중에 선택할 수 있는 2개의 숫자의 조합은 (a,b) , (b,c), (c,a) 이다.
• 이를 통해 다음 숫자를 만들어낸다.
• 다음 숫자를 만들기 전, 현재 숫자가 모두 같은 숫자이면 true를 반환한다.

Node now = q.poll();
int[][] d = { {now.a, now.b, now.c}, {now.b, now.c, now.a} };
if (now.a == now.b && now.b == now.c) {
    return 1;
}
for (int k = 0; k < 3; k++) {
    int na = d[0][k];
    int nb = d[1][k];
    if (na < nb) {
        nb -= na;
        na += na;
    } else if (na > nb) {
        na -= nb;
        nb += nb;
    }
    int nc = sum - (na + nb);
}

• 두 개만 구하면 자동적으로 다음 레벨의 다른 하나의 숫자는 sum을 통해 구할 수 있다.
• visit 배열은 2개의 숫자로만 판단하는데, 세개의 숫자중 가장 큰 숫자와 가장 작은 숫자가 있으면, 중간 숫자 역시 sum을 통해 정해져있기 때문에 visit 배열은 2차원 배열로 생성하였다.

int max = Math.max(Math.max(na, nb), nc);
int min = Math.min(Math.min(na, nb), nc);
if (!visit[max][min]) {
    visit[max][min] = true;
    q.add(new Node(na, nb, nc));
}

• 생각보다 풀고나니 간단했던 문제였다.
• 전체 코드를 첨부한다.

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

public class Main {
    private static int sum = 0;
    private static boolean[][] visit = new boolean[1500][1500];
    private static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(input.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        sum = a + b + c;
        q.add(new Node(a, b, c));
        System.out.println(bfs());
    }
    private static int bfs() {
        while (!q.isEmpty()) {
            Node now = q.poll();
            int[][] d = { {now.a, now.b, now.c}, {now.b, now.c, now.a} };
            if (now.a == now.b && now.b == now.c) {
                return 1;
            }
            for (int k = 0; k < 3; k++) {
                int na = d[0][k];
                int nb = d[1][k];
                if (na < nb) {
                    nb -= na;
                    na += na;
                } else if (na > nb) {
                    na -= nb;
                    nb += nb;
                }
                int nc = sum - (na + nb);
                int max = Math.max(Math.max(na, nb), nc);
                int min = Math.min(Math.min(na, nb), nc);
                if (!visit[max][min]) {
                    visit[max][min] = true;
                    q.add(new Node(na, nb, nc));
                }
            }
        }
        return 0;
    }
    private static class Node {
        int a, b, c;
        Node(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
}