⭕️[BOJ]14712 - 넴모넴모 (Easy) (G5)

문제 링크

14712-넴모넴모 (Easy)

입력

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

출력

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

문제 풀이

혼자 힘으로 풀진 못하고 구글링을 좀 했다
다시 풀라면 또 헷갈리고 정확히 못 풀 것 같은 느낌?
복습하면서 익숙해지기!

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

public class Main {
    static int[][] maps;
    static int N, M, answer = 0;

    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());
        maps = new int[N + 1][M + 1];

        dfs(0);
        System.out.println(answer);
    }

    static void dfs(int cnt) {
        if (cnt == N * M) {
            answer++;
            return;
        }

        int x = cnt / M + 1;
        int y = cnt % M + 1;

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