[BOJ 12886] 돌 그룹 (Java)

BOJ 12886 돌 그룹

문제풀이

이렇게 간단한 문제가 힘들게 할 수 있다니... 많이 배워가는 문제다.

• 처음 생각
  간단하다. 그냥 시키는대로 다 하면 된다. 방문체크하면서 BFS로 구현하자.
  
• 개선
  • 3차원 배열 방문체크는 메모리초과, 현재 돌 그룹을 Set에 저장하자.
  • 돌 그룹을 정렬하면 6가지에서 3가지로 줄일 수 있다.
  • 총 갯수를 3으로 나누어 떨어지지 않으면 같은 숫자의 세 그룹으로 나눌 수 없다.
• 배운점
  • 순서가 바뀌어도 상관없는 상태라면 정렬해서 방문체크하자.
  • 충격적이게도 Set에 int[] 보다 String을 저장하는 것이 더 빠르다. 많이! 이 문제에서 int[]을 쓰면 시간초과다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static Queue<int[]> q;
	static HashSet<String> set;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		q = new LinkedList<>();
		set = new HashSet<>();
		
		int a = stoi(st.nextToken());
		int b = stoi(st.nextToken());
		int c = stoi(st.nextToken());
		
		// 3등분 할 수 없다면 불가하다. 
		if((a + b + c) % 3 != 0) {
			System.out.println(0);
			return;
		}
		
		int[] arr = {a, b, c};
		Arrays.sort(arr);
		
		set.add("" + arr[0] + arr[1] + arr[2]);
		q.offer(arr);
		
		System.out.println(bfs());
	}
	
	private static int bfs() {
		int[] arr;
		while(!q.isEmpty()) {
			int[] now = q.poll();
			
			// 세 그룹의 돌 갯수가 같으면 중지 
			if(now[0] == now[1] && now[1] == now[2]) {
				return 1;
			}
			
			// a - b
			if(now[0] != now[1]) {
				arr = new int[3];
				arr[0] = now[0] + now[0];
				arr[1] = now[1] - now[0];
				arr[2] = now[2];
				
				if(arr[1] > 0) {
					Arrays.sort(arr);
					
					String temp = "" + arr[0] + arr[1] + arr[2];
					if(!set.contains(temp)) {
						set.add(temp);
						q.offer(arr);
					}
				}
			}
			// a - c
			if(now[0] != now[2]) {
				arr = new int[3];
				arr[0] = now[0] + now[0];
				arr[1] = now[1];
				arr[2] = now[2] - now[0];
				
				if(arr[2] > 0) {
					Arrays.sort(arr);
					
					String temp = "" + arr[0] + arr[1] + arr[2];
					if(!set.contains(temp)) {
						set.add(temp);
						q.offer(arr);
					}
				}
			}
            // b - c를 하지 않았을 때 메모리, 시간이 훨씬 절약된다. 근데 왜 하지않아도 되는걸까?
			// b - c
//			if(now[1] != now[2]) {
//				arr = new int[3];
//				arr[0] = now[0];
//				arr[1] = now[1] + now[1];
//				arr[2] = now[2] - now[1];
//				
//				if(arr[2] > 0) {
//					Arrays.sort(arr);
//					
//					String temp = "" + arr[0] + arr[1] + arr[2];
//					if(!set.contains(temp)) {
//						set.add(temp);
//						q.offer(arr);
//					}
//				}
//			}
		}
		return 0;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}