문제 탐색하기

입력 자료 정리

1. n은 격자판의 세로길이, m은 격자판의 가로길이다

해결방법 추론

1. n과 m이 각각 25라면 이야기가 달라지겠지만, 다행히도 nxm의 최대값이 25이다
2. 따라서 백트래킹으로 각 격자판을 선택했을때랑 안했을 때를 구분하도록 하고,
   격자판이 조건을 만족하는지 체크하면 쉽게해결할 수 있을 것이라 생각하였다

시간복잡도 계산

1. 시간복잡도는 2^(nxm)의 연산이 발생할 것 이라 생각하였다
2. n x m만큼 탐색하면서 선택한 경우와 선택하지 않은 경우로 나뉘기 때문이다
3. 따라서 시간복잡도는 O(2^(nxm))이며, 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 크기를 나타내는 n과 m은 변수로 관리한다
2. 그리고 격자판 상태를 나타낼 배열을 하나 선언한다
3. 크기는 n x m이고 보관하는 상태는 있냐 없냐 두가지이기에 boolean타입의 배열로
   관리하였다
4. 그리고 정답을 위한 ans 변수를 0으로 초기화하여 미리 세팅해둔다

백트래킹 설계

1. 먼저 조건을 만족시키는지 확인한다. 조건을 만족시킨다면 ans의 값을 증가시킨다
2. 재귀식을 실행하기 위한 탐색은 start부터 n x m까지다
3. 이중포문은 복잡하기에 2차원 배열을 하나의 포문으로 돌도록 하였다
4. 세로좌표는 현재 탐색 인덱스인 i에 가로길이인 m을 나눈 몫이며,
   가로좌표는 현재 탐색 인덱스인 i에 가로길이인 m을 나눈 나머지다.
5. 이어서 방문을 안했으면 방문체크후 재귀, 이후 방문체크 해제를 하면 된다

함수식

- backtracking(int depth, int start, int n, int m)
1. 탐색 범위를 위해 depth,n,m을 파라미터로 받는다
2. 또한 탐색의 시작 위치를 위해 start를 파라미터로 받는다

재귀식

- backtracking(depth+1, i+1, n, m)
1. 재귀식으로 깊이를 증가시켜주며, 현재 탐색지점의 다음 지점으로 start 인수를 넘겨준다

base condition

- if(depth == n x m){return;}
1. 탐색의 종료지점인 n x m에 depth가 도달한다면 백트래킹을 종료한다

넴모넴모 조건 검증 메소드 설계

1. ans 증가를 위한 조건 검증 메소드를 하나 만들어줘야한다
2. boolean 타입으로 리턴하면 되며, n과 m을 파라미터로 받는다
3. n-1, m-1만큼 이중포문을 돌며 탐색한다
4. 이때 현재위치, 우측, 아래, 우측아래대각선 위치의 배열의 값이 모두 true라면
   false를 리턴하며 나머지는 true를 리턴한다

출력값 설계

1. 이렇게 완성한 ans를 출력하면 정답이 된다.

정답 코드

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] visited;
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        visited = new boolean[n][m];

        backtracking(0, 0,n,m);
        bw.write(ans+"");

        br.close();
        bw.close();
    }

    private static void backtracking(int depth, int start, int n, int m) {
        if(chk(n, m)){
            ans++;
        }
        if(depth == n * m){
            return;
        }
        for (int i = start; i < n*m; i++) {
            int r = i / m;
            int c = i % m;
            if(!visited[r][c]){
                visited[r][c] = true;
                backtracking(depth+1,i+1,n,m);
                visited[r][c] = false;
            }

        }

    }

    private static boolean chk(int n, int m) {

        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < m - 1; j++) {
                if(visited[i][j] && visited[i][j+1] && visited[i+1][j] && visited[i+1][j+1]){
                    return false;
                }
            }
        }
        return true;

    }
}

문제 링크

14712번 - 넴모넴모 (Easy)