백준 : 12886

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

12886번: 돌 그룹

 

boolean 형을 잘못생각하면 1000 1000 1000 구조로 해야하나 생각 할수 있다.

이렇게 제출하면 메모리초과 오류를 발생시킨다.

따라서 문제를 자세히보면 a b c 의 총량은 항상 일정하다는것을 알수있다. 따라서 2개의 값이정해지면 나머지하나의 값은 전체에서 두개를 빼주는 아이디어로 메로리초과를 방지할수가있다.

 
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class B12886 {
    static int Answer = 0;
 
    static class Pair {
        int a;
        int b;
 
        public Pair(int a, int b) {
            super();
            this.a = a;
            this.b = b;
        }
    }
 
    static int sum = 0;
    static boolean visit[][] = new boolean[1001][1001];
 
    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;
        Solve(a, b);
        System.out.println(Answer);
    }
 
    public static void Solve(int a, int b) {
        if (sum % 3 != 0)
            return;
 
        BFS(a, b);
    }
 
    public static void BFS(int a, int b) {
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(a, b));
        visit[a][b] = true;
 
        while (!q.isEmpty()) {
            Pair cur = q.poll();
            int x = cur.a;
            int y = cur.b;
            int z = sum - x - y;
            if (x == y && y == z) {
                Answer = 1;
                break;
            }
 
            if (x > y) {
                if (y + y <= 1000 && !visit[x - y][y + y]) {
                    visit[x - y][y + y] = true;
                    q.add(new Pair(x - y, y + y));
                }
            }
 
            if (x < y) {
                if (x + x <= 1000 && !visit[x + x][y - x]) {
                    visit[x + x][y - x] = true;
                    q.add(new Pair(x + x, y - x));
                }
            }
 
            if (x > z) {
                if (z + z <= 1000 && !visit[z + z][x - z]) {
                    visit[z + z][x - z] = true;
                    q.add(new Pair(z + z, x - z));
                }
            }
 
            if (x < z) {
                if (x + x <= 1000 && !visit[x + x][z - x]) {
                    visit[x + x][z - x] = true;
                    q.add(new Pair(x + x, z - x));
                }
            }
 
            if (y > z) {
                if (z + z <= 1000 && !visit[z + z][y - z]) {
                    visit[z + z][y - z] = true;
                    q.add(new Pair(z + z, y - z));
                }
            }
 
            if (y < z) {
                if (y + y <= 1000 && !visit[y + y][z - y]) {
                    visit[y + y][z - y] = true;
                    q.add(new Pair(y + y, z - y));
                }
            }
        }
 
    }
}