[ BOJ ][JAVA][14712] 넴모넴모

www.acmicpc.net/problem/14712

14712번: 넴모넴모 (Easy)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	208	127	105	69.079%

문제

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

코드

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

public class p14712 {
    static int n, m, answer = 0;
    static boolean[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new boolean[33][33];

        dfs(1, 1);
        System.out.println(answer);
    }

    static void dfs(int r, int c) {
        if (r == n && c == m + 1) {
            answer++;
            return;
        }
        for (int i = r; i <= n; i++) {
            for (int j = (i==r ? c : 1); j <= m; j++) {
                if (check(i, j)) continue;

                map[i][j] = true;
                dfs(i, j + 1);
                map[i][j] = false;
            }
        }
        answer++;
    }

    static boolean check(int r, int c) {
        return map[r-1][c] && map[r][c-1] && map[r-1][c-1];
    }
}

다른 풀이

import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
    static int [][]map;
    static int N, M;
    static int answer;
    static public void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        map = new int[N + 1][M + 1]; // 1-index

        dfs(0);
        System.out.println(answer);
    }
    static void dfs(int cnt) {
        if(cnt == N * M) {
            answer ++;
            return ;
        }
        int y = cnt / M + 1;
        int x = cnt % M + 1;

        if(map[y - 1][x] == 1 && map[y][x - 1] == 1 && map[y - 1][x - 1] == 1) { // 현재 놓을 수 없는 곳
            dfs(cnt + 1);
        }
        else {
            dfs(cnt + 1); // 선택 안하고 다음껄 볼 경우
            map[y][x] = 1;
            dfs(cnt + 1); // 선택 하고 다음껄 볼 경우
            map[y][x] = 0;
        }
    }
}