백준 12886 돌 그룹 (Java)

1. 문제 링크

12886번: 돌 그룹

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. A, B, C를 입력받고, 만들 수 있는 돌 개수로 2차운 배열을 만든다.

2. 3 그룹의 합이 3의 배수가 아니라면 같은 개수로 나눌 수 없다.

3. DFS 탐색을 진행하며 A, B, C가 같은 개수가 나오는지 확인한다.

    3-1. A와 B, B와 C, C와 A를 각 단계에서 전부 비교해보면서 나오는지 확인한다.

    3-2. 방문 배열을 통해 작은 값과 큰 값이 나왔었는지 확인하고, 그 값들로 DFS 탐색을 진행한다.

 

4. 코드

import java.io.IOException;
import java.util.Scanner;

public class Main {
	static boolean[][] visit;
	static int result;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		visit = new boolean[1501][1501];
		
		if((A+B+C)%3 != 0) { //3 그룹으로 나눠지는지
			result = 0;
		}
		else {
			dfs(A, B, C);
		}
		
		System.out.println(result);
	}

	private static void dfs(int a, int b, int c) {
		if(a==b && b==c) {
			result = 1;
			return;
		}
		
		check(a, b, c);
		check(b, c, a);
		check(c, a, b);		
	}

	private static void check(int g1, int g2, int etc) {
		int min = Math.min(g1, g2);
		int max = Math.max(g1, g2);
		
		if(!visit[min+min][max-min]) {
			visit[min+min][max-min] = true;
			dfs(min+min, max-min, etc);
		}
	}
    
}