백준 > 12886번 > 돌 그룹 BFS, DFS - JAVA

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

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

 

 

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

 

 

 

코드

BFS 풀이 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class JUN12886 {
    static int sum;
    static boolean[][] visited;

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

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        sum = A + B + C;
        visited = new boolean[sum+1][sum+1];

        if(sum % 3 != 0){
            System.out.println("0");
            return;
        }

        Queue<int[]> q = new ArrayDeque<>();

        q.offer(new int[]{A,B,C});
        visited[A][B] = true;

        boolean flag = false;
        while (!q.isEmpty()){
            int[] now = q.poll();
            int a = now[0];
            int b = now[1];
            int c = now[2];

            if(a == b && b == c) {
                flag = true;
                break;
            }

            for (int i = 0; i < 2; i++) {
                for (int j = i+1; j < 3; j++) {
                    if(now[i] == now[j]) continue;
                    int t1 = now[i] > now[j]? now[i] - now[j] : now[i] + now[i];
                    int t2 = now[i] > now[j]? now[j] + now[j] : now[j] - now[i];
                    if(!visited[t1][t2]){
                        visited[t1][t2] = true;
                        q.offer(new int[]{t1, t2 ,sum - (t1 + t2)});
                    }
                }
            }
        }

        System.out.println(flag?"1":"0");
    }
}

DFS 풀이 방식

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

public class Main {
    static int sum;
    static int[][] visited;

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

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        sum = A + B + C;
        visited = new int[sum+1][sum+1];

        if(sum % 3 != 0){
            System.out.println("0");
        }else {
            dfs(A,B);
            System.out.println(visited[sum/3][sum/3]);
        }
    }

    public static void dfs(int a, int b){
        if(visited[a][b] == 1) return;

        visited[a][b] = 1;

        int[] now = {a, b, sum - (a+b)};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(now[i] < now[j]) {
                    int[] temp = {a, b, sum - (a + b)};
                    temp[i] += now[i];
                    temp[j] -= now[i];
                    dfs(temp[0], temp[1]);
                }
            }
        }
    }
}

 

풀이

 

 A + B + C = sum 

이 세가지 돌 그룹의 합은

돌을 이동 시켜도 변하지 않는다.

 

또한

C = sum - ( A + B)

와 같이 

한 돌 그룹의 값은

sum 값에서 나머지 두 그룹의 합을 뺀 값과 같다

 

 두 그룹을 비교하다 보면

결국 반복된다.

-> 중복 처리 필요

 

다음에 또 봐요