백준 12886 (돌 그룹) - java

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

12886번: 돌 그룹

문제 : 

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

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

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

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

 

유형 : 그래프 탐색

 

접근

• 방문 배열을 3차원으로 할 경우 메모리 초과를 감당할 수 없게 된다.
• 가장 중요한 접근은 방문 배열이 2차원이여도 문제가 없다는 것이다.
  • 전체 돌의 개수는 고정적이다. 가장 큰 개수의 돌과 가장 작은 개수의 돌을 안다면 전체 돌의 개수에서 2개의 값을 뺀다면 중간 돌의 개수도 고정적이라는 것이다.
• 위 접근을 기반으로 방문 배열을 2차원으로 하여 v[작은 돌의 개수][큰 돌의 개수]로 설정하자

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static int k = 0;

    static boolean[][] v;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        v = new boolean[1500][1500];


        bfs();
        br.close();
    }

    static void bfs(){
        Queue<Group> q = new LinkedList<>();
        q.add(new Group(n,m,k));
        v[Math.min(n,Math.min(m,k))][Math.max(n,Math.max(m,k))] = true;

        while(!q.isEmpty()){
            Group cur = q.poll();

            if(cur.x == cur.y && cur.y == cur.z){
                System.out.println(1);
                return;
            }

            // 1 ,2
            if(cur.x != 0 && cur.y !=0){
                int nx = 0;
                int ny = 0;

                if(cur.x < cur.y){
                    nx = cur.x + cur.x;
                    ny = cur.y - cur.x;
                }
                else if(cur.x > cur.y){
                    nx = cur.x - cur.y;
                    ny = cur.y + cur.y;
                }

                int min = Math.min(Math.min(nx,ny),cur.z);
                int max = Math.max(Math.max(nx,ny),cur.z);

                if(!v[min][max]){
                    v[min][max] = true;
                    q.add(new Group(nx,ny,cur.z));
                }
            }
            // 1, 3
            if(cur.x !=0 && cur.z !=0) {
                int nx = 0;
                int nz = 0;

                if (cur.x < cur.z) {
                    nx = cur.x + cur.x;
                    nz = cur.z - cur.x;
                } else if (cur.x > cur.z) {
                    nx = cur.x - cur.z;
                    nz = cur.z + cur.z;
                }

                int min = Math.min(Math.min(nx,cur.y),nz);
                int max = Math.max(Math.max(nx,cur.y),nz);

                if(!v[min][max]){
                    v[min][max] = true;
                    q.add(new Group(nx,cur.y,nz));
                }
            }
            // 2, 3
            if(cur.y!=0 &&cur.z !=0) {
                int ny = 0;
                int nz = 0;
                if (cur.y < cur.z) {
                    ny = cur.y + cur.y;
                    nz = cur.z - cur.y;
                } else if (cur.y > cur.z) {
                    ny = cur.y - cur.z;
                    nz = cur.z + cur.z;
                }

                int min = Math.min(Math.min(cur.x,ny),nz);
                int max = Math.max(Math.max(cur.x,ny),nz);

                if(!v[min][max]){
                    v[min][max] = true;
                    q.add(new Group(cur.x,ny,nz));
                }
            }
        }

        System.out.println(0);
    }
}
class Group{
    int x;
    int y;
    int z;

    Group(int x,int y,int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }
}