네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 비어 있는 칸을 임의로 골라 “넴모”를 하나 올려놓거나, “넴모”가 올라간 칸 네 개가 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 해줍니다.
