[백준] 12886번 : 돌 그룹 Gold5(골드 5) - JAVA[자바]

[Gold IV] 돌 그룹 - 12886

문제 링크

성능 요약

메모리: 50696 KB, 시간: 196 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2023년 11월 21일 10:59:00

문제 설명

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 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을 출력한다.

 

 

풀이 방식

1. 돌의 개수를 전부 같게 만들어야 함.

2. 만약 총 합을 3으로 나눈 나머지가 0이 아니라면 return 0;

3. 돌의 개수는 변하지 않기 때문에 2차원 배열을 사용하면 나머지 돌의 개수 자동으로 알 수 있다.(두개의 합 + 없는 숫자 -> 총 합)

4. 개수가 다르면 연산하고 방문을 표시함(방문한 곳을 또 계산해도 의미가 없기 때문에) 방문 배열을 통해서 계산을 안해본 경우만 계산 하고 큐에 삽입해준다.

5. 큐에 넣어주는 경우는?

 - X, Y를 비교했을 때 값이 다른 경우 && 방문하지 않은 경우

6. While문이 종료될 때까지(큐가 빌 때까지) 값이 같지않다면 return

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[3];
        for(int i = 0 ; i < 3; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(bfs(arr));
    }

    private static int bfs(int[] arr) {
        // 합이 3으로 나누어지지 않는다면 결과는 0
        int sum = arr[0] + arr[1] + arr[2];
        if(sum % 3 != 0){
            return 0;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(arr);

        // 방문하는 배열은 2차원 배열이여도 됨 why? 어차피 돌의 개수는 고정이니까 두개의 합 + 나머지의 합 -> 총합
        boolean[][] visit = new boolean[sum+1][sum+1];
        visit[arr[0]][arr[1]] = true;

        while(!queue.isEmpty()){
            int[] ns = queue.poll();
            int x = ns[0];
            int y = ns[1];
            int z = ns[2];

            // 3개가 모두 같다면 return 1
            if(x == y && y == z){
                return 1;
            }

            /*
                개수가 다르면 연산을 처리 후 방문을 했다고 남김(만약 방문한 곳을 또 방문(연산한 값을 또 연산)하는 것은 의미가 없기 때문에
                방문 배열을 통해서 계산 안해본 경우만 계산 후 큐에 삽입
             */
            // 갯수가 다른 연산
            if(x != y){
                int nx = x > y ? x - y : x + x;
                int ny = x > y ? y + y : y - x;

                if(!visit[nx][ny]){
                    queue.offer(new int[] {nx,ny,z});
                    visit[nx][ny] = true;
                }
            }
            if(y != z){
                int ny = y > z ? y - z : y + y;
                int nz = y > z ? z + z : z - y;

                if(!visit[ny][nz]){
                    queue.offer(new int[] {x,ny,nz});
                    visit[ny][nz] = true;
                }
            }
            if(x != z){
                int nx = x > z ? x - z : x + x;
                int nz = x > z ? z + z : z - x;

                if(!visit[nx][nz]){
                    queue.offer(new int[]{nx,y,nz});
                    visit[nx][nz] = true;
                }
            }
        }

        return 0;
    }
}