[백준] 14712 넴모넴모 2 java 풀이

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/14712

(1) 조건 분석 📊

• 배열 내에 2 * 2짜리 부분 배열 모든 값이 1이면 넴모넴모 라고 한다.
• 배열 내 각 좌표에 1 아니면 0을 둘 수 없을 때, 넴모넴모가 없는 경우의 수를 구하라

2. 코드가 나오기까지 🛠️

KEY WORD: 백트래킹

배열의 한 좌표씩 0과 1을 두어보면서 확인하면 된다.
끝까지 계산한 뒤에, 넴모넴모 있는지 여부를 체크하면, 계산 과정에서 이미 무효한 경우의 수도 끝까지 세어야함으로 비효율적이다.

따라서 계산 과정에서 넴모넴모를 만나면 그 이후의 경우의 수를 거치지 않는다. 이런 식으로 그때 그때 계산하면, 훨씬 효율적이다.

(1) 시간복잡도 분석 ⏳

$N \times M <= 25$ 이기 때문에 25개의 좌표밖에 생기지 않는다.
따로 시간복잡도를 신경 쓸 필요는 없는 것 같다.

3. 코드 🌐

(1) SUDO CODE 💬

// 간단한 의사 코드

0. 기저 조건 행이 배열을 벗어나면 return
1. 다음 좌표 계산하기 -> 열을 벗어나면 다음 행 맨 왼쪽 좌표로 지정
2. 현재 좌표에 1을 넣었을 떄, 넴모넴모가 되는가?
    (1) 되면, 현 좌표에 0을 넣은 경우만 다음 DFS를 돈다.
    (2) 안되면 현 좌표에 0을 넣은 경우, 1을 넣은 경우 전부 DFS를 돈다.

(2) JAVA CODE ☕

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

public class Main {
    static int R,C;
    static int ans = 0;
    static int [][] b;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        b = new int [R][C];
        back_tracking(0,0);
        System.out.println(ans);
    }

    public static void back_tracking(int row, int col) {
        if(row == R) {
            ans++;
            return;
        }
        int nr = (col == C-1)? row+1 : row;
        int nc = (col == C-1)? 0 : col+1;
        back_tracking(nr,nc);

        if(!isNemoNemo(row,col) && !OOB(row,col)) {
            b[row][col] = 1;
            back_tracking(nr, nc);
            b[row][col] = 0;
        }
    }

    private static boolean isNemoNemo(int r, int c){
        if(OOB(r-1, c-1)) return false;
        if(b[r-1][c] == 1 && b[r-1][c-1] == 1 && b[r][c-1] == 1) return true;
        return false;
    }

    private static boolean OOB(int r, int c){
        return r < 0 || c < 0 || r >= R || c >= C;
    }
}

4. 트러블 슈팅 or 배운 점📝

(1) 백 트래킹 풀며 자주 실수하는 부분

• 언제 값을 산정할 지 정하는 것이 아직 서툴다.
• 계산 끝나고 값 원상복구를 하지 않는 경우가 많다.