[백준,c++] 14712번 - 넴모넴모 (Easy)

문제

14712번: 넴모넴모 (Easy)

 

코드

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

int N, M, ans;

int map[26][26];
int dx[3] = {-1,0,-1};
int dy[3] = {0,-1,-1};

bool check(int x, int y){
    int cnt = 0;
    for(int i = 0; i<3; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx>=0 && nx < N && ny>=0 && ny< M){
            if(map[nx][ny]) cnt++;
        }
    }
    if(cnt == 3) return false;
    return true;
}


void backtracking(int x, int y){
    
    if(x == N-1 && y == M){
        ans++;
        return;
    }
    
    if(y == M){
        y = 0;
        x++;
    }
    
    map[x][y] = 1;
    if(check(x, y)) backtracking(x, y+1);   // 2*2가 안 만들어질때 넴모를 올린다.
    map[x][y] = 0;
    backtracking(x, y+1);   // 현재칸에는 넴모를 올리지않고 넘어간다.
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;

    backtracking(0,0);
    
    cout<<ans;
}

 

풀이

처음에 문제를 이해하기가 조금 어려웠는데 이 문제는 넴모가 2*2가 만들어지지 않는 모든 경우의 수를 출력하는 문제입니다. 

넴모를 놓는 순서는 다음과 같습니다.

---

넴모

넴모	넴모

넴모	넴모	넴모

넴모	넴모	넴모
넴모

넴모	넴모	넴모
넴모		넴모

경우의 수 카운팅++

---

즉, 가로에 먼저 넴모를 배치하게끔 구현했습니다. 이 방식으로 놓으면 현재 놓은 넴모를 기준으로 좌측, 상측, 좌측 대각선 이 세 개만 넴모인지를 확인하면 2*2 넴모가 만들어지는지를 판별할 수 있습니다.

현재 위치에 넴모를 놓았을 때 2*2가 만들어지면 현재 상황에서는 이 위치에서는 놓지 않는 경우만 존재합니다.

2*2가 만들어지지 않는다면 이 위치에 놓는경우와 놓지 않는 경우가 존재합니다.

이런 식으로 백트랙킹을 돌려서 최종적으로 모든 경우의 수를 출력하면 됩니다.