[BackTracking] boj 14712 java "넴모넴모 (Easy) "

넴모넴모 (Easy) 성공출처

 

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

512 MB

300

170

130

69.149%

문제

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

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

입력

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

출력

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

예제 입력 1 복사

2 2

예제 출력 1 복사

15

예제 입력 2 복사

2 3

예제 출력 2 복사

57

예제 입력 3 복사

3 5

예제 출력 3 복사

22077

 

1) (0,0)을 마지막으로 탐색할 때

package BackTracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj14712_넴모넴모 {

	static int[][] map;
	static int N, M;
	static int count;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String temp[] = br.readLine().split(" ");

		N = Integer.parseInt(temp[0]);
		M = Integer.parseInt(temp[1]);
		
		map = new int[N+1][M+1]; // 1-index
		
		dfs((N*M) -1);	//15
		System.out.println(count);
	}

	/* 1. 각 칸 마다 조회
	 * 2. 각 칸 차례일 때 각 칸에 네모가 (있을 때, 없을때)
	 * 3. 현재 칸에 네모를 놓았는데 주변에 3개가 있을 때 그냥 패스 -> 못 두는 경우
	 * 4. 네모를 존재 여부 -> 모든 칸 조회 한 후 (count++)
	 */
	
	public static void dfs(int cnt) {
		if(cnt == -1  ) {
			count++;
			return;
		}
		
		int x = cnt / M;	//열로 나눈다.
		int y = cnt %M;
		
//		x 1 0
//		x x 0
//		0 0 0
		
		System.out.println(x + " "+y);
		
		if(!(map[x][y+1]==1 && map[x+1][y]==1 && map[x+1][y+1]==1) ) {
			//현재칸 선택 x
			//현재 칸 선택
			map[x][y] = 1;
			dfs(cnt-1);
			
			//현캐 칸 선택 x
			map[x][y] = 0;
			}
		dfs(cnt-1);
						
		
	}

}

 

2) (n,m) 을 마지막으로 탐색할 때

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static int[][] map;
	static int N, M;
	static int count;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String temp[] = br.readLine().split(" ");

		N = Integer.parseInt(temp[0]);
		M = Integer.parseInt(temp[1]);
		
		map = new int[N+1][M+1]; // 1-index
		
		dfs(0);
		System.out.println(count);
	}

	/* 1. 각 칸 마다 조회
	 * 2. 각 칸 차례일 때 각 칸에 네모가 (있을 때, 없을때)
	 * 3. 현재 칸에 네모를 놓았는데 주변에 3개가 있을 때 그냥 패스 -> 못 두는 경우
	 * 4. 네모를 존재 여부 -> 모든 칸 조회 한 후 (count++)
	 */
	
	public static void dfs(int cnt) {
		if(cnt == N*M) {
			count++;
			return;
		}
		
		int x = cnt / M + 1;	//열로 나눈다.
		int y = cnt %M + 1;
		
		if(map[x][y-1]==1 && map[x-1][y]==1 && map[x-1][y-1]==1) {
			//현재칸 선택 x
			dfs(cnt+1);
		}
		else {
			//현재 칸 선택
			map[x][y] = 1;
			dfs(cnt+1);
			
			//현캐 칸 선택 x
			map[x][y] = 0;
			dfs(cnt+1);
		}
						
		
	}

}

[해설]

1. "넴모"가 존재할 수 있는 모든 경우의 수에서 "넴모" 가 2by2로 존재하는 경우를 제외시켜줘야 합니다.

2. 다르게 생각하면, 넴모가 2x2가 되는 경우의 수만 제외시켜주고 모든 경우의 수를 count 해줍니다.

3. 현재 칸으로 부터 어떤 방향으로 4각 네모를 탐색할지를 결정합니다.

4. 현재 조회하는 칸에 네모를 둘 경우와 네모를 두지 않을 경우, 2가지를 조회합니다.