[백준] 12886 돌그룹

문제

---

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

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

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

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

 

 

 

풀이

---

우선 돌을 오름차순으로 정렬을 한뒤 각각의 오른쪽 돌과의 값을 교환한 뒤에 해당 수조합이 없다면 queue에 넣어주는 방식을 이용하여 문제를 풀었다.

 

알고리즘 순서는 다음과 같다.

1. 주어진 세개의 돌의 조합을 오름차순으로 정렬한 뒤 Queue 에 넣어주고 그 때의 수조합을 String으로 만들어 Set에 넣어준다.
2. 조합 알고리즘을 이용하여 작은수에서 큰수를 a + a, b - a 를 해준 수조합이 Set에 없다면 Queue 에 넣어준다.
3. 모든 수가 동일하다면 return 1 을 하고 아니라면 Queue 가 빌때까지 1번을 다시 반복한다.
4. Queue.isEmpty() 인데 메서드가 끝나지 않으면 return 0 을 해주면 된다.

 

BFS 탐색을 하는 코드는 아래와 같다.

while(!queue.isEmpty()) {
	
	int[] top = queue.poll();
	
	if(isTrue(top)) {
		return 1;
	}
	
	for(int i = 0 ; i < 2 ; i++) {
		for(int j = i + 1 ; j < 3 ; j++) {
			
			int a = top[i];
			int b = top[j];
			
			if(b - a <= 0 ) { continue ;}
			
			top[i] = a + a;
			top[j] = b - a;
            
            int[] result = new int[3];
			result = top.clone();
            Arrays.sort(result);
			if(set.add(arrayToString(result))) {
				queue.add(result);
			}
			top[i] = a;
			top[j] = b;
		}
	}			
}

 

여기서 아래 코드를 이용해서 배열을 String 화 시켜주었다.

static String arrayToString(int[] arr) {
	
	String result = "";
	
	for(int i = 0 ; i < 3; i++) {
		result += arr[i] + " ";
	}
	
	return result;
}

 

 

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	static int[] stone;
			
	static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		
		stone = new int[3];
		for(int i = 0 ; i < 3 ; i++) {
			stone[i] = parseInt(st.nextToken());
		}
			
		System.out.println(solution());
	}
	
	static int solution() {
		
		Queue<int[]> queue = new LinkedList<>();
		Set<String> set = new HashSet<>();
        
        Arrays.sort(stone);
		queue.add(stone);
		set.add(arrayToString(stone));
		while(!queue.isEmpty()) {
			
			int[] top = queue.poll();
			
			if(isTrue(top)) {
				return 1;
			}
			
			for(int i = 0 ; i < 2 ; i++) {
				for(int j = i + 1 ; j < 3 ; j++) {
					
					int a = top[i];
					int b = top[j];
					
					if(b - a <= 0 ) { continue ;}
					
					top[i] = a + a;
					top[j] = b - a;
		            
		            int[] result = new int[3];
					result = top.clone();
		            Arrays.sort(result);
					if(set.add(arrayToString(result))) {
						queue.add(result);
					}
					top[i] = a;
					top[j] = b;
				}
			}			
		}		
		
		return 0;
	}
	
	static boolean isTrue(int[] arr) {
		
		int a = arr[0];
		for(int i = 1 ; i < 3; i++) {
			if(arr[i] != a) {
				return false;
			}
		}
		
		return true;
	}
	
	static String arrayToString(int[] arr) {
		
		String result = "";
		
		for(int i = 0 ; i < 3; i++) {
			result += arr[i] + " ";
		}
		
		return result;
	}
	
}