[백준] 12886 돌 그룹 - BFS JAVA

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

12886번: 돌 그룹

코드설명

BFS 문제입니다.

 

처음에는 DFS 문제 혹은 백트래킹 문제인줄 알았으나, BFS로 모든 경우의 수를 판단하는 것이 가장 쉽게 풀 수 있을 것 같아 해당 방안으로 진행했습니다.

 

문제에서 유의해야할 점입니다.

1. A + B + C 가 3 으로 나눠지지 않는다면 모든 돌이 같은 수로 될 수 없습니다.
2. Visited[2001][2001] 선언을 통해 방문처리합니다. (visited[501][501][501] 을 통해 진행할경우 메모리 초과가 발생합니다.) 여기서 2001 인 이유는 a , b 가 존재할떄 더 작을경우 a + a 가 진행됩니다. 연속적으로 a가 더 작은경우가 2번 발생할 수 있으므로 최악의 경우를 상정하여 500 -> 1000 -> 2000 이라 생각하여 위와 같이 선언하였습니다.

 

여기서 visited[][] 를 같이 공유하는것이 이해가 가지 않을 수 있습니다.

이유는, 결국 3가지 A, B, C 그룹이 어떤 그룹이냐는것이 중요하지않고, 3가지 그룹 중에 2가지 그룹이 정해지면 1가지 그룹은 무조건 정해지기에 위와 같이 생각할 수 있습니다.

 

그 외에는 a와 b를 비교, b와 c를 비교, a와 c를 비교하면 됩니다.

//개수가 다른 두개 골라서 연산
if(a != b) {
    int na = a > b ? a - b : a + a;
    int nb = a > b ? b + b : b - a;

    if(visited[na][nb] == false) {
        q.offer(new Node(na, nb, c));
        visited[na][nb] = true; //
    }
}

if(b != c) {
    int nb = b > c ? b - c : b + b;
    int nc = b > c ? c + c : c - b;
    if(visited[nb][nc] == false) {
        q.offer(new Node(a, nb, nc));
        visited[nb][nc] = true;
    }
}

if(a != c) {
    int na = a > c ? a - c : a + a;
    int nc = a > c ? c + c : c - a;
    if(visited[na][nc] == false) {
        q.offer(new Node(na, b, nc));
        visited[na][nc] = true;
    }
}

만약 visited[501][501][501]을 통해 진행할경우 위와 똑같은 상황에서 Visited[][][] 만 수정해주면 됩니다.

 

코드

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

public class Main {
	
	public static int A, B, C;
	public static boolean[][] visited;
	public static int answer = 0;
    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());
    	
    	if( (A + B + C) % 3 != 0) { //3개의 합이 3으로 나눠지지 않는경우 돌의 개수를 같게 만들 수 없습니다. 3개가 모두 같아지려면 3의 배수여야합니다.
    		System.out.println("0");
    		return ;
    	}
        
    	simulate();
    	System.out.println(answer);
    }
    
    public static void simulate() {
    	Queue<Node> q = new LinkedList<>();
    	
    	//돌 그룹. 처음에는 visited[1001][1001] 이라고 생각했지만, 하나에 연속으로 값이 더해질 수 있으므로, 
    	boolean[][] visited = new boolean[2001][2001];
    	
    	q.offer(new Node(A, B, C));
    	visited[A][B] = true;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int a = temp.a;
    		int b = temp.b;
    		int c = temp.c;
    		
    		if(a == b && b==c) {
    			answer = 1;
    			return ;
    		}
    		
    		//개수가 다른 두개 골라서 연산
    		if(a != b) {
    			int na = a > b ? a - b : a + a;
    			int nb = a > b ? b + b : b - a;
    			
    			if(visited[na][nb] == false) {
    				q.offer(new Node(na, nb, c));
    				visited[na][nb] = true; //
    			}
    		}
    		
    		if(b != c) {
    			int nb = b > c ? b - c : b + b;
    			int nc = b > c ? c + c : c - b;
    			if(visited[nb][nc] == false) {
    				q.offer(new Node(a, nb, nc));
    				visited[nb][nc] = true;
    			}
    		}
    		
    		if(a != c) {
    			int na = a > c ? a - c : a + a;
    			int nc = a > c ? c + c : c - a;
    			if(visited[na][nc] == false) {
    				q.offer(new Node(na, b, nc));
    				visited[na][nc] = true;
    			}
    		}
    		
    	}
    	
    }
}

class Node{
	int a;
	int b;
	int c;
	public Node(int a, int b, int c) {
		this.a=a;
		this.b=b;
		this.c=c;
	}
}