백준 12886 돌 그룹 [JAVA]

 

해당 문제는  bfs , dfs로 모두 풀이가 가능하다.

• 모든 경우의 수를 따져봐야하지만 세 수의 합이 3의 배수일 때  세 수가 같아질 수 있다는 특징을 가지고 있다.
• 또한 세 수의 합은 언제나 같으므로 3차원이 아니 2차원만으로도 방문여부를 확인할 수 있다.
• 3차원으로 선언해 버리면 메모리 초과 오류가 발생해 버린다.

 

bfs 풀이

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

class Main{

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int a = Integer.parseInt(s[0]);
        int b = Integer.parseInt(s[1]);
        int c = Integer.parseInt(s[2]);
        boolean[][] visit = new boolean[1501][1501];

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{a,b,c});
        while(!queue.isEmpty()){
            int[] t = queue.poll();
            visit[t[0]][t[1]] = true;
            if(t[0] == t[1] && t[1] == t[2]){
                System.out.println("1");
                return;
            }
            Arrays.sort(t);
            int tmpA = 2*t[0];
            int tmpB = t[1] - t[0];
            int tmpC = t[2];
            if(check(tmpA, tmpB, tmpC, visit)) queue.add(new int[]{tmpA, tmpB, tmpC});
            tmpA = 2*t[0];
            tmpB = t[1];
            tmpC = t[2]  - t[0];
            if(check(tmpA, tmpC, tmpB, visit)) queue.add(new int[]{tmpA, tmpC, tmpB});
            tmpA = t[0];
            tmpB = t[1]*2;
            tmpC = t[2]  - t[1];
            if(check(tmpC, tmpB, tmpA, visit)) queue.add(new int[]{tmpC, tmpB, tmpA});
        }

        System.out.println("0");
    }
    static boolean check(int a, int b, int c, boolean[][] visit){
        if(visit[a][b]) return false;
        int sum = a + b + c;
        if(sum % 3 == 0) {
            visit[a][b] = true;
            return true;
        }
        return false;
    }
}

 

 

dfs 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main{
    static int ans = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int a = Integer.parseInt(s[0]);
        int b = Integer.parseInt(s[1]);
        int c = Integer.parseInt(s[2]);
        boolean[][] visit = new boolean[1501][1501];


        if(a == b && b == c){
            System.out.println("1");
            return;
        }
        visit[a][b] = true;
        dfs(a, b, c, visit);
        dfs(a, c, b, visit);
        dfs(b, c, a, visit);


        System.out.println(ans);
    }
    static void dfs(int a, int b, int c, boolean[][] visit){
        if(a == b && b == c){
            ans = 1;
            return;
        }
        int na = Math.max(a,b);
        int nb = Math.min(a,b);
        a = na - nb;
        b = nb*2;
        if(visit[a][b]) return;
        int sum = a + b + c;

        if(sum % 3 == 0) {
            visit[a][b] = true;
            dfs(a, b, c, visit);
            dfs(a, c, b, visit);
            dfs(a, b, c, visit);
        }

    }
}