[백준/BOJ] 14712번 넴모넴모 (Easy) 자바 풀이

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

14712번: 넴모넴모 (Easy)

문제

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

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

입력

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

출력

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

 

 

 

격자판의 최대가 작으므로 브루트포스를 통해 풀 수 있다.

DFS로 depth가 0부터 N*M인 경우를 모두 탐색하고,

탐색할 때마다 격자판에 없앨 수 있는 넴모가 있는지 확인한다.

없앨 수 있는 넴모가 있다면 게임을 그만두지 못하므로 answer를 갱신하지 않고,

없앨 수 있는 넴모가 있다면 게임을 그만둘 수 있으므로 answer에 1을 더해준다.

 

이때 숫자를 방문했는지 나타내는 visit 배열이 격자판을 의미한다.

visit가 true, 즉 방문했다면 넴모가 있는 것이고 false면 넴모가 없이 빈 공간인 것이다.

visit가 true인 원소가 2*2 사각형을 이룬다면 없앨 수 있는 넴모가 존재한다고 판단했다.

 

 

0부터 N*M-1까지 숫자를 뽑는 방식으로 DFS를 진행했는데,

만약 2*2에서 013을 뽑는 것과 130을 뽑는 건 동일한 격자판이므로

중복된 원소를 허용하지 않도록 DFS의 전달인자로 어느 숫자부터 뽑을지 정해주는 start를 전달했다.

 

 

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

public class Main {
	static int N, M;
	static boolean[][] visit;
	static int answer = 0;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		visit = new boolean[N][M];
		DFS(0, 0);
		
		System.out.println(answer);
	}
	
	static void DFS(int depth, int start) {
		// 넴모가 0개부터 N * M개까지 존재할 수 있으므로 모든 경우를 카운트
		answer += check(depth) ? 1 : 0; 
		if(depth == N * M) // 넴모를 모두 채운 경우 DFS 끝내기
			return;

		for(int i=start;i<N*M;i++) {
			int r = i / M;
			int c = i % M;
			if(visit[r][c])
				continue;
			visit[r][c] = true;
			DFS(depth + 1, i + 1);
			visit[r][c] = false;
		}
		
	}
	
	// 없앨 수 있는 넴모가 없으면 true, 있으면 false
	static boolean check(int depth) {
		if(depth < 4) // 넴모가 세개 이하인 경우 없앨 수 없음
			return true;
		
		for(int i=0;i<N-1;i++)
			for(int j=0;j<M-1;j++) 
				if(visit[i][j] && visit[i][j + 1] && visit[i + 1][j] && visit[i + 1][j + 1])
					return false;
		return true;
	}

}