[백준] 12886번 : 돌 그룹

12886번: 돌 그룹

---

[BFS]

브루트포스로 푼다면 문제 자체의 난이도는 비교적 간단한 편이나, 브루트 포스로 푼다면 메모리 소모가 엄청나므로 최대한 효율적인 방법으로 중복 점을 제거하여야 한다. 여러 방법이 있을 수 있다.

 

나는 정렬을 사용했다. 브루트 포스를 사용한다면 방문을 체크하는 정점 배열을 [1501][1501][1501] 만큼의 배열을 사용해야하지만, 정렬을 사용하면 [501][1001][1501] 정도의 크기로 줄일 수 있다. 돌의 개수는 최대 1500개를 넘지 않으니 말이다.

# Code </>

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

public class Main {

    static boolean[][][] visit = new boolean[501][1001][1501];

    static int BFS(int[] start){
        Queue<int[]> Q = new LinkedList<>();

        visit[start[0]][start[1]][start[2]] = true;
        Q.add(start);

        while(!Q.isEmpty()){
            int[] val = Q.poll();

            if(val[0] == val[2]) return 1;

            for(int a=0; a<3; a++){
                int[] nVal = {val[0], val[1], val[2]};
                int cur = a;
                int next = (cur+1) % 3;

                if(nVal[cur] == nVal[next]) continue;
                if(next == 0){
                    cur = 0;
                    next = 2;
                }

                nVal[next] -= nVal[cur];
                nVal[cur] *= 2;

                Arrays.sort(nVal);
                if(!visit[nVal[0]][nVal[1]][nVal[2]]){
                    visit[nVal[0]][nVal[1]][nVal[2]] = true;
                    Q.add(nVal);
                }
            }
        }
        return 0;
    }

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

        int[] val = new int[3];
        for(int i=0; i<3; i++)
            val[i] = Integer.parseInt(st.nextToken());

        Arrays.sort(val);
        System.out.println(BFS(val));
    }
}