[JAVA] 백준 12886번 돌 그룹

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

12886번: 돌 그룹

이 글을 쓰는 이유는, 문제를 복습하면서 다시 푸는데 바로 생각해내지 못한 부분이 있어서(부끄럽지만)

그 부분을 기록해서 잊어버리지 않고 다음에는 비슷한 문제를 만났을 때 바로 풀기 위해서이다.

 

돌 그룹 문제는 세 그룹의 돌을 동일한 수로 나누는 문제인데,

세 그룹의 돌의 전체 개수가 정해져 있다는 점을 이용해야 메모리와 시간을 아낄 수 있는 문제이다.

무조건 문제를 풀기 시작하는게 아니라 정해진 돌의 개수에서 그룹을 나눈다는 점을 이용해 효율적으로 풀어야 하는 문제인데 이부분을 이전에 풀었음에도 복습할때 바로 생각해내지 못했다. 그래서 이제는 절대 잊지 않기 위해 기록한다.

 

나는 너비우선탐색, BFS(Breadth-First Search) 방법으로 문제를 풀었다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

        int sum = a + b + c;
        if(sum%3 != 0) {
            System.out.println(0);
            return;
        }

        int max = sum+1;
        boolean[][] check = new boolean[max][max];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {a,b,c});
        boolean pass = false;
        while(!q.isEmpty()) {
            int[] temp = q.poll();
            int x = temp[0];
            int y = temp[1];
            int z = temp[2];

            if(x >= max || y >= max || z >= max) continue;
            if(x < 0 || y < 0 || z < 0) continue;
            if(x==y && y==z && z==x) {
                pass = true;
                break;
            }
            if(check[x][y]) continue;

            check[x][y] = true;
            for(int i=0; i<3; i++) {
                for(int j=0; j<3; j++) {
                    for(int k=0; k<3; k++) {
                        if(i==j || j==k || k==i) continue;
                        q.add(new int[] {temp[i]+temp[i], temp[j]-temp[i], temp[k]});
                    }
                }
            }
        }

        if(pass) {
            System.out.println(1);
        }else {
            System.out.println(0);
        }

    }
}

 

 

돌의 개수가 정해져 있는 점을 이용하여 코드를 짜는 방법이 있었다.

 

너비우선탐색을 시작하기 전에, 돌을 세그룹으로 나눌수 있는지 없는지를 먼저 확인할 수 있다.

전체 돌의 개수를 3으로 나누었을때 나머지가 0인지 아닌지에 따라서 너비우선탐색을 시작할 필요가 있는지, 없는지를 먼저 확인할 수 있는 것이다. 돌 개수의 합이 3으로 나누어떨어지지 않으면, 너비우선탐색을 시작할 필요 없이 바로 끝내면 됐다.

 

돌을 규칙에 따라 3등분으로 나눌 때 나누어진 돌의 개수가 기존에 있었던 경우를 또다시 만나게 되면,

도돌이표처럼 또 같은 규칙에 따라 분배하는 것을 반복하기 때문에 boolean 배열 변수를 사용하여 체크를 하는데,

이 때! 돌의 그룹이 3그룹이라고 해서 3차원으로 배열을 선언할 필요가 없다.

전체 돌의 개수가 같다는 점을 이용하면, 1그룹, 2그룹의 돌의 개수가 정해지면 3번째 그룹의 돌의 개수도 정해지기 때문에 boolean을 이차원 배열로 선언하여 그 값을 기록한다면, 모든 경우의 수를 기록할 수 있다.

전체 : sum / 1그룹 : x / 2그룹 : y / 3그룹 : sum - x - y

 

위 두가지만 잘 기억한다면 바로 풀 수 있는 문제이다.

다음부터는 문제의 전제를 잘 활용해서 효율적으로 푸는 방법을 바로 생각해 내야겠다.