[백준] 14712 넴모넴모 (Java)

문제설명

1. 격자판의 비어 있는 칸을 임의로 골라 "넴모"를 하나 올려놓거나, "넴모"가 올라간 칸 네 개가 2 x 2사각형을 이루는 부분을 찾아 그 위에 있는 "넴모"들을 모두 없애는 것을 계속 반복한다. 
2. 넴모가 사라지지 않는 배치의 가짓수를 계산하라

조건

- 최대 5 x 5 배열

문제 해결 프로세스

1. DFS로 네모를 하나씩 놓고 네모가 생성되었는지 체크
2. 네모가 생성되었다면 종료
3. 그렇지 않다면 정답 + 1

코드

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


public class Main {
    static int N, M;
    static boolean[][] visit;
    static int 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());
        visit = new boolean[N][M];
        DFS(0);
        System.out.println(answer);

    }
    public static void DFS(int depth) {
        if(depth == N * M) {
            if(check()) answer++;
            return;
        }
        int x = depth / M;
        int y = depth % M;


        DFS(depth + 1);
        visit[x][y] = true;
        DFS(depth + 1);
        visit[x][y] = false;

    }

    public static boolean check() {
        for(int i = 0; i< N - 1; i++) {
            for(int j = 0; j< M - 1; j++) {
                if(visit[i][j] && visit[i][j + 1] && visit[i + 1][j] && visit[i + 1][j + 1]) return false;
            }
        }
        return true;
    }


}

정리

해당 코드는 가지치기가 되지 않았다. 넴모를 놓았을 때 해당 위치가 이미 2 x 2인지 체크 한 후 제거해도 될 듯하다.