BOJ G4 12886 돌그룹 JAVA

12886번: 돌 그룹

---

문제 읽기

처음 문제를 읽고 예제를 한 번 그려봤다.

위와 같은 과정을 통해서 이루어진다면 돌이 정확히 분배된다.

 

위에서 알 수 있는 점은, 세 그룹에 있는 돌의 합이 3으로 나누어 떨어지지 않는다면 무조건 0을 출력한다는 점과, 이 문제는 다른 알고리즘 보다는 완전 탐색을 해야 할 것 같다는 느낌(?)이다.

 

그래서 완전 탐색인 DFS를 통해서 풀어보았다.

---

문제 풀기

처음 작성했던 풀이 과정은 크게 복잡하진 않았다.

 

우선 세 그룹을 두 그룹씩 개수를 비교해서 다음 함수로 넘겨주는 과정을 작성했다. 이렇게 하면 무한 루프에 빠질 위험성이 높기 때문에, 그룹 A, B, C에 대해서 3차원 방문 배열을 만들었다.

 

그렇게 하고 답을 내니까 답은 맞았다. 그런데 뭔가.. 답이 나오는 속도가 너무 너무 느렸다. 그리고 400 500 399 같이 큰 수를 넣어보면 스택 오버플로우가 발생했다. 제출도 해보니 1퍼센트에서 메모리초과가 났다.

 

어떤 게 문제일까 고민하다가 방문 배열에 대해 개선점을 찾았다. 기존에는 A, B, C를 각각의 그룹으로, used[A][B][C]만 확인했다. 하지만 어쨌든 used[B][A][C] 와 같이 똑같은 ‘상황’이 있었다면, 그룹의 이름을 무시한다 했을 때 똑같은 상황이 반복될 것이다. 그래서 notVisited라는 메서드를 추가해 이런 같은 ‘상황’을 나타내는 것들을 다 걸러주었다.

    private static boolean notVisited(int a, int b, int c) {
        return !used[a][b][c] && !used[a][c][b] &&!used[b][a][c] &&!used[b][c][a] &&!used[c][a][b] &&!used[c][b][a];
    }

 

하지만 그래도 메모리 초과였다. 정확한 원인을 알기 어려워서 검색을 해봤다. 블로그를 참고하니, 다들 방문 배열을 2차원으로만 선언했다. 그룹이 A, B, C로 세 개이지만, 두 그룹의 개수만 알면 나머지 그룹의 개수는 자동으로 알 수 있다. 빠지거나 더해지는 돌이 없기 때문이다. 그래서 이 부분을 참고해서 나도 방문 배열을 2차원으로 바꿔주었다.

그러니 통과했다!

 

아마 방문 배열의 크기가 150115011501이라서 처음에 속도가 그렇게 느렸던 것 같다. 해당 문제의 메모리 제한은 512MB이다. boolean은 1바이트이다.

512MB = 512 * 10^6 = 512000000(약 5억)

150115011501 = 3,375,000,000(약 30억)

 

512MB는 약 5억 정도이고, 3차원으로 선언한 배열의 크기는 약 30억이다. 이제 보니 당연히 안되는 것… 이걸 놓치지 말자!

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.StringTokenizer;

public class BOJ_G4_12886_돌그룹 {
    static int N = 1501;
    static boolean[][] used = new boolean[N][N];
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        if ((A + B + C) % 3 != 0) System.out.println(0);
        else System.out.println((move(A, B, C))? 1 : 0);
    }

    private static boolean move(int a, int b, int c) {
//        System.out.println(a + " " + b + " " + c);
        if (a == b && b == c) return true;

        boolean isOk = false;
        if (a != b){
            if (a > b && notVisited(a-b, b+b, c)){
                used[a-b][b+b] = true;
                isOk = move(a-b, b+b, c);
            }
            else if (a < b && notVisited(a+a,b-a,c)){
                used[a+a][b-a] = true;
                isOk = move(a+a, b-a, c);
            }
        }
        if (isOk) return isOk;

        if (a != c){
            if (a > c && notVisited(a-c,b,c+c)){
                used[a-c][b] = true;
                isOk = move(a-c, b, c+c);
            }
            else if (a < c && notVisited(a+a, b, c-a)){
                used[a+a][b] = true;
                isOk = move(a+a, b, c-a);
            }
        }
        if (isOk) return isOk;

        if (b != c){
            if (b > c && notVisited(a, b-c, c+c)){
                used[a][b-c] = true;
                isOk = move(a, b-c, c+c);
            }
            else if (b < c && notVisited(a, b+b, c-b)){
                used[a][b+b] = true;
                isOk = move(a, b+b, c-b);
            }
        }
        return isOk;
    }

    private static boolean notVisited(int a, int b, int c) {
        return !used[a][b] && !used[a][c] &&!used[b][a] &&!used[b][c] &&!used[c][a] &&!used[c][b];
    }
}