[JAVA] 백준 - 돌그룹 12886

www.acmicpc.net/problem/12886

12886번: 돌 그룹

 

# 2개의 그룹의 돌 개수를 알면 나머지 한 그룹의 돌 개수는 자동으로 정해진다.

따라서 2차원 배열로 방문체크를 해도된다.

 

예를 들어, { 4, 5, 6 } 의 돌 그룹이 있다고 하자.

 

그러면  check[4][5] 만 하면된다. 반대로 check[5][6]을 했다면 check[4][5]는 필요없다.

 

또한 순서도 상관없다. check[4][5] 를 하거나 check[5][4]를 하거나 똑같다. 왜냐면 4,5,6 이나 5,4,6이나 6,5,4 나 모두 같은 경우의 수로 취급하기 때문이다.

 

우리는 모든 그룹의 돌개수가 같은지만 확인하면 되지 순서는 상관없다.

 

 

# 현재 상태에서 다음 상태의 경우의 수는??

{ a,b, c } 의 돌 그룹이 있다고 가정하자.

 

1) a와 b를 조작하고 다음 상태로 가는 경우

2) b와 c를 조작하고 다음 상태로 가는 경우

3) a와 c를 조작하고 다음 상태로 가는 경우

 

총 3가지가 있다. 

 

# 전체코드

import java.util.*;

class Main{
    static int sum;
    static boolean[][] ch = new boolean[1501][1501];
    static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        sum = a + b + c;

        ch[a][b] = true;
        dfs(a,b);
        System.out.println(answer);

    }

    public static void dfs(int a,int b){
        int c = sum - a - b;
        if(a == b && b == c ){
            answer = 1;
            return;
        }
        go(a,b);
        go(b,c);
        go(a,c);

    }

    private static void go(int a, int b) {
        int small = Math.min(a,b);
        int big = Math.max(a,b);
        if(!ch[small *2][big - small] || !ch[big - small][small *2]){
            ch[small *2][big - small] = ch[big - small][small *2] = true;
            dfs(small*2, big-small);
        }
    }


}