[BOJ 14712] 넴모넴모 (Easy) - java

백준 14712번: 넴모넴모 (Easy)

풀이

👉 2 x 2 사각형이 존재하지 않는 모든 넴모 배치 경우의 수

💡 DFS 탐색을 하며, 현 위치에 넴모를 둔다, 안 둔다로 가지를 쳐서 탐색을 한다!

But, 넴모를 안 두는 경우는 그냥 안 두고 DFS 타면 되지만

넴모를 두는 경우에는 해당 자리에 넴모를 둠으로써 2 x 2 사각형이 생기는지 확인해주어야 한다!

이때, int[][] map 을 활용하여 (x, y)에 넴모가 있으면 1, 없으면 0으로 표기한다.

(x, y) 기준으로 사각형이 생기는지는 (x, y) 기준 사각형을 만드는 4개의 칸의 map[x][y] 합이 4가 되는지 확인한다.

private static boolean check(int x, int y) { // (x, y)를 기준으로 2 x 2 사각형이 생기는지 체크
    if (map[x - 1][y - 1] + map[x - 1][y] + map[x][y - 1] + map[x][y] == 4 ||
        map[x - 1][y] + map[x - 1][y + 1] + map[x][y] + map[x][y + 1] == 4 ||
        map[x][y - 1] + map[x][y] + map[x + 1][y - 1] + map[x + 1][y] == 4 ||
        map[x][y] + map[x][y + 1] + map[x + 1][y] + map[x + 1][y + 1] == 4
    ) return true;
    return false;
}

그리고 map은 new int[N + 2][M + 2] 로 선언하여 범위를 사각형 탐색시 범위를 벗어나는 상황을 고려하지 않도록 한다.

전체 코드

public class BOJ_14712 {

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

    private static void dfs(int x, int y) {
        if (x == N && y == M) {
            // 현재 위치에 넴모를 두지 않는 경우
            answer++;

            // 현재 위치에 넴모를 두는 경우
            map[x][y] = 1;
            if (!check(x, y)) answer++;
            map[x][y] = 0;
            return;
        }
        // 현재 위치에 넴모를 두지 않는 경우
        if (y == M) dfs(x + 1, 1);
        else dfs(x, y + 1);

        // 현재 위치에 넴모를 두는 경우
        map[x][y] = 1;
        if (!check(x, y)) {
            if (y == M) dfs(x + 1, 1);
            else dfs(x, y + 1);
        }
        map[x][y] = 0;
    }

    private static boolean check(int x, int y) { // (x, y)를 기준으로 2 x 2 사각형이 생기는지 체크
        if (map[x - 1][y - 1] + map[x - 1][y] + map[x][y - 1] + map[x][y] == 4 ||
            map[x - 1][y] + map[x - 1][y + 1] + map[x][y] + map[x][y + 1] == 4 ||
            map[x][y - 1] + map[x][y] + map[x + 1][y - 1] + map[x + 1][y] == 4 ||
            map[x][y] + map[x][y + 1] + map[x + 1][y] + map[x + 1][y + 1] == 4
        ) return true;
        return false;
    }

    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 int[N + 2][M + 2]; // 사각형 체크할 때 범위 벗어나는 거 쉽게 계산하기 위해 + 2
        dfs(1, 1);
        System.out.println(answer);
    }
}