백준 14172 넴모넴모

링크

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

문제 조건은 격자판에 넴모들이 올라간 칸이 2*2 사각형을 이루지 않는 모든 배치의 가짓수를 구하는 것이다.

문제를 보면 열의 개수 N, 행의 개수 M이 1 <= N\*M <= 25가 공백으로 주어진다. dfs로 푸는 전형적인 문제다.
처음에는 이걸 수학으로 풀어야 하나 정말 고민하다가 다른 코드를 참고해서 풀었다. 근데 찾아보니까 다 코드가 비슷비슷 하다..

키 아이디어는 맵 (0,0)부터 (N,M)까지 한칸씩 옆으로 가면서 넴모를 놓지 않는 경우, 놓는 경우를 모두 카운트 하는 것이다. 그래서 (N,M)까지 도달했을 때 ans++ 해준다.
이 때 현재 칸을 기준으로 대각선 윗칸, 윗칸, 왼쪽 옆칸이 채워져 있으면 현재 칸에는 넴모를 놓지 못한다. 그럴 경우는 무조건 넴모를 놓지 않아야 하기 때문에 map을 빈칸으로 두고 함수를 호출한다.

또 헷갈렸던 게 왜 cnt를 기준으로 진행되는가 였다. 이건 취향차인거 같은데 cnt를 기준으로 r, c 좌표를 계산하는게 살짝 낯설었다.

int r = cnt / M + 1;
int c = cnt % M + 1;

기억하자! 왼쪽에서 오른쪽으로 진행하기 때문에 행 개수인 M으로 나눠준다.
2*3 map에서 cnt가 4이면 (1,1)이 돼야 한다. (처음 칸의 cnt를 0으로 하기 때문에) 그리고 여기선 범위를 벗어났는지 체크를 안해주려고 N+1, M+1 사이즈로 잡아서 +1씩 해준다.

package boj;

import java.io.IOException;
import java.util.Scanner;

public class boj_14712 {
    static int N, M, ans = 0;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N+1][M+1];

        backtracking(0);

        System.out.println(ans);
    }
    public static void backtracking(int cnt){
        if(cnt == M * N){
            ans++;
            return;
        }
        int r = cnt/M + 1;
        int c = cnt%M + 1;

        if(map[r-1][c] == 1 && map[r][c-1] == 1 && map[r-1][c-1] == 1){
            backtracking(cnt+1);
        }else{
            backtracking(cnt+1);
            map[r][c] = 1;
            backtracking(cnt+1);
            map[r][c] = 0;
        }

    }
}

이건 범위 체크 하고 map을 N*M으로 만든 버전

package boj;

import java.io.IOException;
import java.util.Scanner;

public class boj_14712 {
    static int N, M, ans = 0;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N][M];

        backtracking(0);

        System.out.println(ans);
    }
    public static void backtracking(int cnt){
        if(cnt == M * N){
            ans++;
            return;
        }
        int r = cnt/M ;
        int c = cnt%M ;

        if(0 <= r-1 && 0 <= c-1 && map[r-1][c] == 1 && map[r][c-1] == 1 && map[r-1][c-1] == 1){
            backtracking(cnt+1);
        }else{
            backtracking(cnt+1);
            map[r][c] = 1;
            backtracking(cnt+1);
            map[r][c] = 0;
        }

    }
}