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

문제

2x2 사각형을 이루지 않는 배치의 가짓수 구하기

풀이

N = 25, M = 25로 모든 조합의 수를 확인하기에 충분한 시간복잡도이므로
백트래킹을 이용해 모든 경우의 수를 확인한다

코드

private static void nemo(int r, int c) {
        if (r == N) {
        	// 만약 r이 N이 되어서 수를 돌았으면 
            // 배치된 넴모들이 2 x 2 를 이루는지 확인 => 4 칸(2 x 2) 씩 확인
            for (int i = 0; i <= N - 2; i++) {
                for (int j = 0; j <= M - 2; j++) {
                    // 2 x 2 를 이루는 경우
                    if (map[i][j] && map[i][j+1] &&
                            map[i+1][j] && map[i+1][j+1])
                        return;
                }
            }

            answer++;
            return;
        }

nemo(0,0) -> nemo(0,1) -> ... -> nemo(0,m) -> ... -> nemo(n,0) 이 되면 재귀함수를 끝낼 수 있도록 return

만약 사각형을 이루면 바로 return
이루지 않으면 answer++

        int nextCol = (c + 1 == M) ? 0 : c + 1;
        int nextRow = (nextCol == 0) ? r + 1 : r;

nemo(0,0) -> nemo(0,1) -> ... -> nemo(0,m) -> ... -> nemo(n,0) 이 될 수 있도록 nextCol과 nextRow를 선언

		map[r][c] = true;
        nemo(nextRow, nextCol);
        map[r][c] = false;
        nemo(nextRow, nextCol);

넴모가 있는 경우와 넴모가 없는 경우 두가지로 재귀 함수를 호출

전체 코드

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

public class Main {

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

	// 입력
    public static void input() {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        M = fr.nextInt();
        map = new boolean[N][M];
    }

    private static void nemo(int r, int c) {
        if (r == N) {
            // 배치된 넴모들이 2 x 2 를 이루는지 확인 => 4 칸(2 x 2) 씩 확인
            for (int i = 0; i <= N - 2; i++) {
                for (int j = 0; j <= M - 2; j++) {
                    // 2 x 2 를 이루는 경우
                    if (map[i][j] && map[i][j+1] &&
                            map[i+1][j] && map[i+1][j+1])
                        return;
                }
            }

            answer++;
            return;
        }

        int nextCol = (c + 1 == M) ? 0 : c + 1;
        int nextRow = (nextCol == 0) ? r + 1 : r;

        map[r][c] = true;
        nemo(nextRow, nextCol);
        map[r][c] = false;
        nemo(nextRow, nextCol);

    }


    public static void main(String[] args) {
        input();
		nemo(0, 0);
        System.out.println(answer);
    }


	// 입력 보조 함수
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in));}

        String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        Double nextDouble() { return Double.parseDouble(next()); }

        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            } catch(IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}

느낀점

백트래킹은 정해진 틀이 있으므로 백트래킹문제는 그 틀을 많이 벗어나지 않는 것 같다.