[백준] 14172. 넴모넴모 (Easy) - C++

문제

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

• 소요 시간 : 1시간
• 난이도 : 골드 5

접근 방법

백트래킹을 이용하여 모든 경우의 수를 찾는다.

1. 가로로 넴모를 한개씩 놓는다. 가로로 맵의 끝까지 도달했으면 다음 행으로 넘어가서 반복한다. 

2. 넴모를 놓을 때 좌상, 상, 좌측에 넴모가 있는지 체크한다.

- 넴모가 모두 있다면 넴모가 만들어지므로 현재 위치에 넴모를 놓지 않고 넘어간다. 

- 넴모가 모두 있지 않다면 넴모가 만들어지지 않으므로 현재 위치에 넴모를 놓았을 때, 놓지 않았을 때 모두 탐색한다. 

나의 풀이

#include <iostream>

using namespace std;

int N, M; 
// 0 <= y < N (행)
// 0 <= x < M (열)

int answer = 0;
int map[26][26];

// 상, 좌상, 좌
int dx[3] = {0, -1, -1};
int dy[3] = {-1, -1, 0};


bool makeNemmo(int x, int y) {
    int cnt = 0;
    for(int i=0; i<3; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (ny < 0 || ny >= N || nx < 0 || nx >= M)
            continue;

        if (map[ny][nx]) cnt++; 
    }

    return cnt == 3;
}

void backtracking(int x, int y) {

    // 맨 마지막 
    if (x == M && y == N-1) {
        answer++;
        return;
    }

    // 다음 행으로 
    if (x == M) {
        x = 0;
        y++;
    }

    // 넴모 놓기 
    map[y][x] = 1; 

    // 넴모가 만들어지지 않으면 놓은 채로 넘어간다.
    if (!makeNemmo(x, y)) {
        backtracking(x+1, y);
    }

    // 넴모 빼기
    map[y][x] = 0;
    backtracking(x+1, y);
    
}

int main() {
    cin >> N >> M;

    backtracking(0, 0);

    cout << answer;
}

정리

어떻게 풀어야할지 생각이 나지 않아 아래 블로그를 참고하였다.

백트래킹 연습하기! 

참고 

https://dkswnkk.tistory.com/606

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