[백준, BOJ 14712] 넴모넴모 (Easy) (java)

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

14712번: 넴모넴모 (Easy)

---

문제

네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 비어 있는 칸을 임의로 골라 “넴모”를 하나 올려놓거나, “넴모”가 올라간 칸 네 개가 2 × 2 사각형을 이루는 부분을 찾아 그 위에 있는 “넴모”들을 모두 없애는 것을 질릴 때까지 반복하면 된다.

하지만 안타깝게도 게임은 정말 재미가 없었고, 네모는 아주 빨리 질려 버리고 말았다. 실망한 네모는 게임을 적당히 플레이하다가, “넴모”를 없애고 싶은데 격자판 위에 없앨 수 있는 “넴모”가 없으면 게임을 그만두기로 했다. 네모가 게임을 그만두었을 때 나올 수 있는 “넴모”의 배치의 가짓수를 구하여라.

입력

첫 번째 줄에 격자판의 행의 개수 N, 열의 개수 M(1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25)이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 출력한다.

728x90

 

예제 입력 1

2 2

예제 출력 1

15

 

예제 입력 2

2 3

예제 출력 2

57

 

예제 입력 3

3 5

예제 출력 3

22077

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int N;
	static int M;
	static int[][] arr;
	static int result;
	
	private static void nemmo(int x, int y) {
		// 마지막 인덱스인 경우
		if(x == N && y == M) {
			// 현재 인덱스에 넴모를 두지 않는 경우는 일단 배치 가능
			result++;
			
			// 현재 인덱스에 넴모를 두는 경우 없앨 수 있는 넴모가 생겼는지 체크
			arr[x][y] = 1;
			if(!check(x, y)) { // 안생겼다면
				result++;
			}
			arr[x][y] = 0;
			return;
		}
		
		// 현재 인덱스에 넴모를 두지 않는 경우
		// 현재 인덱스에 해당하는 배열 값은 유지한 채 다음 칸으로 넘어감
		if(y == M) nemmo(x + 1, 1);
		else nemmo(x, y + 1);
		
		// 현재 인덱스에 넴모를 두는 경우
		arr[x][y] = 1;
		// 현재 인덱스에 넴모를 둠으로써 없앨 수 있는 넴모가 생겼나 체크
		if(check(x, y)) { // 없앨 수 있는 넴모가 생겼으면 return
			arr[x][y] = 0;
			return;
		}
		else { // 아니라면 다음 인덱스로 넘어감
			if(y == M) nemmo(x + 1, 1);
			else nemmo(x, y + 1);
		}
		arr[x][y] = 0;
	}
	
	private static boolean check(int x, int y) { // 현재 인덱스에 넴모를 둠으로써 없앨 수 있는 넴모가 생겼나 체크
		if(arr[x - 1][y - 1] + arr[x - 1][y] + arr[x][y - 1] + arr[x][y] == 4
				|| arr[x - 1][y] + arr[x - 1][y + 1] + arr[x][y] + arr[x][y + 1] == 4
				|| arr[x][y - 1] + arr[x][y] + arr[x + 1][y - 1] + arr[x + 1][y] == 4
				|| arr[x][y] + arr[x][y + 1] + arr[x + 1][y] + arr[x + 1][y + 1] == 4)
			return true; // 없앨 수 있는 넴모가 생겼다면 true
		return false; // 아니라면 false
	}

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		// N, M 입력
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		// N x M 배열
		arr = new int[N + 2][M + 2];
		
		// 넴모 배치 가짓수 구하기
		nemmo(1, 1);
		
		// 답 출력
		System.out.println(result);
	}

}