[BOJ/C++] 14712: 넴모넴모

🥇 Gold 5

✏️ 최종 솔루션

⭐️ 백트래킹

1. (0,0) 부터 현재 위치에 네모를 놓는 경우와 놓지 않는 경우를 나누어 DFS
2. 현재 위치가 마지막 위치라면 하나의 루트를 찾은 것이기 때문에 가짓수 count
   ❗️ 가중치가 아니라 가짓수를 세는 것이기 때문에 마지막 위치 도달할 때마다 count 해주기만 하면 됨
3. 현재 위치가 y 의 마지막 위치라면 다음 행으로 위치를 옮겨주기
4. 현재 위치를 놓으면 2*2 가 완성되는지 확인
   1) 왼쪽에서 오른쪽으로 순차적으로 탐색하기 때문에 현재 위치를 놓음으로써 2*2 가 완성되려면 왼쪽, 윗쪽, 왼쪽 대각선 위의 자리를 방문했어야 함
   현재 위치 놓을 수 없다면 skip
   2) 현재 위치 놓을 수 있다면 방문 처리하고 다음 자리 이어서 탐색
5. 현재 위치 방문 처리 해제
6. 다음 자리 탐색

📌 self feedback

백트래킹으로 가능한 가짓수를 count 하는 게 관건
기본적으로 현재 위치에 네모를 올릴 수 없다고 가정하고 2*2 를 완성하지 않는 경우에만 네모 올리기
백트래킹으로 최소경로를 찾는 문제만 많이 풀이했어서 가짓수만 count 하는 방안은 익숙하지 않았음
현재 위치가 마지막 자리인 경우와 현재 위치가 열의 끝 자리인 경우를 처리해주는 시점이 헷갈렸음

✏️ 최종 code

#include <iostream>
#include <vector>
using namespace std;

int n,m,ans=0;
bool visit[26][26]={false};

// 좌, 상, 왼쪽 대각선 위
int dx[3]={0,-1,-1};
int dy[3]={-1,0,-1};

void dfs(int x, int y) {
    // 현재 위치가 마지막 위치인 경우
    if(x==n-1 && y==m) {
        ans++;
        return;
    }
        
    // 현재 위치가 y 끝인 경우
    if(y==m) {
        y=0;
        x++;
    }
    
    // 현재 위치가 2*2 만듦
    bool pass=true;
    for(int i=0;i<3;i++) {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(!visit[nx][ny]) {
            pass=false;
            break;
        }
    }
    
    visit[x][y]=true;
    if(!pass) dfs(x,y+1);    // 네모 올리기
    
    visit[x][y]=false;
    //default: 지나침
    dfs(x,y+1);
}

int main() {
    cin >> n >> m;
   
    visit[0][0]=true;
    dfs(0,0);
    
    cout << ans;
    
}