문제

BOJ 12886: 돌 그룹 https://www.acmicpc.net/problem/12886

풀이

조건

• 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다.
• 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.
• 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.
  • 크기가 같지 않은 두 그룹을 고른다.
  • 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다.
  • X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
  • 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

풀이 순서

• BFS를 사용하여 해결했다.
• 세 그룹의 합이 3으로 나눠지지 않으면 false를 반환한다.
• Queue에 처음 상태를 삽입한다.
• Queue에서 차례로 뽑아내며 갯수가 다른 2개를 골라 연산을 한다.
• 방문 처리를 해줄 boolean배열의 크기는 1501로 해준다.
  • 문제에서 돌 갯수의 합이 최대 1500이기 때문이다.
  • 3차원이 아닌 2차원으로 한 이유는 총 돌의 갯수는 변하지 않기 때문에 2개의 그룹만 알아도 남은 1개의 그룹을 알 수 있기 때문이다.

코드

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

public class Main {
    
	static int A, B, C;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    	A = Integer.parseInt(st.nextToken());
    	B = Integer.parseInt(st.nextToken());
    	C = Integer.parseInt(st.nextToken());
    	
    	// true: 1 출력, false: 0 출력
    	System.out.println(bfs(A, B, C) ? 1 : 0);
    }
    
    static boolean bfs(int a, int b, int c) {
    	
    	// 세 그룹의 합이 3으로 안 나눠지면 false
    	if((a + b + c) % 3 != 0) return false;
    	
    	Queue<Stone> que = new LinkedList<>();
    	boolean[][] isChecked = new boolean[1501][1501];
    	
    	que.add(new Stone(a, b, c));
    	isChecked[a][b] = true;
    	
    	while(!que.isEmpty()) {
    		Stone s = que.poll();
    		
    		a = s.a;
    		b = s.b;
    		c = s.c;
    		
    		// 세 개가 모두 같아지면 true 반환
    		if(a == b && b == c) {
    			return true;
    		}
    		
    		// 갯수가 다른 두 개 골라서 연산
    		if(a != b) {
    			int na = a > b ? a-b : a+a;
    			int nb = a > b ? b+b : b-a;
    			
    			if(!isChecked[na][nb]) {
    				que.add(new Stone(na, nb, c));
    				isChecked[na][nb] = true;
    			}
    		}
    		
    		if(b != c) {
    			int nb = b > c ? b-c : b+b;
    			int nc = b > c ? c+c : c-b;
    			
    			if(!isChecked[nb][nc]) {
    				que.add(new Stone(a, nb, nc));
    				isChecked[nb][nc] = true;
    			}
    		}
    		
    		if(a != c) {
    			int na = a > c ? a-c : a+a;
    			int nc = a > c ? c+c : c-a;
    			
    			if(!isChecked[na][nc]) {
    				que.add(new Stone(na, b, nc));
    				isChecked[na][nc] = true;
    			}
    		}
    		
    	}
    	
    	// Queue가 끝나도 3개가 모두 같아지지 않으면 false 반환
    	return false;
    }
    
    static class Stone{
    	int a, b, c;
    	
    	Stone(int a, int b, int c){
    		this.a = a;
    		this.b = b;
    		this.c = c;
    	}
    }
  
}

정리

• 방문 처리를 3차원이 아닌 2차원으로만 해도 된다.
• 방문 처리를 해 줄 배열의 크기를 (500 * 3) / 2 로 해줬다.