[백준/실버1] 14712. 넴모넴모 (Easy)

문제

---

문제

네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 비어 있는 칸을 임의로 골라 “넴모”를 하나 올려놓거나, “넴모”가 올라간 칸 네 개가 2 × 2 사각형을 이루는 부분을 찾아 그 위에 있는 “넴모”들을 모두 없애는 것을 질릴 때까지 반복하면 된다.

하지만 안타깝게도 게임은 정말 재미가 없었고, 네모는 아주 빨리 질려 버리고 말았다. 실망한 네모는 게임을 적당히 플레이하다가, “넴모”를 없애고 싶은데 격자판 위에 없앨 수 있는 “넴모”가 없으면 게임을 그만두기로 했다. 네모가 게임을 그만두었을 때 나올 수 있는 “넴모”의 배치의 가짓수를 구하여라.

입력

첫 번째 줄에 격자판의 행의 개수 N, 열의 개수 M(1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25)이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 출력한다.

풀이

---

접근 방식

• 일단 문제의 이해가 약간 어려웠는데, 네모가 게임을 그만두었을 때나올 수 있는 배치의 가짓수를 구하는 것이다.
• 칸에 넴모가 있거나/없거나 이기 때문에 부분집합으로 모든 경우를 구한다고 생각했다.
• 재귀 함수를 사용하는데, 왼쪽 위→ 아래로 채우면서 모든 칸을 다 고려했을 때가 기저조건이다.
• 행과 열의 개수가 2525 이기 때문에.. 2^(2525) 는 너무나도 커서 백트래킹이 필수이다.
• 현재 고려하고 있는 칸을 채웠을 때 2x2 사각형의 일부가 된다면 return ⇒ 백트래킹
• ⇒ 왼쪽→오른쪽, 위→아래 방향으로 격자를 고려하기 때문에.. 내가 확인할 주변의 칸은 왼쪽, 왼쪽위, 위 뿐이다.
• 2x2 사각형이 되는 조건(터지는 조건)
  • 고려하고 있는 칸은 채워져 있어야 한다.
  • 왼쪽, 왼쪽 위, 위 칸이 채워져 있어야 한다.

코드

---

package practice;

import java.util.Scanner;

// [실버1] 넴모넴모 (Easy)
// 네모가 게임을 그만두었을 때 나올 수 있는 “넴모”의 배치의 가짓수를 구하여라.
// 왼->오 위->아래 채우기
// 부분집합 + 백트래킹
public class baekjoon_14712 {
    static int N, M;
    static int cnt;
    static boolean[][] map;
    static int[] dx = {0, -1, -1};
    static int[] dy = {-1, -1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        cnt = 0;
        map = new boolean[N][M];

        map[0][0] = true;
        subset(0);
        map[0][0] = false;
        subset(0);

        System.out.println(cnt);
    }

    // 왼, 왼위, 위를 확인한다.
    private static void subset(int num) {

        int x = num / M;
        int y = num % M;

        boolean flag = true; // 터질 수 있으면 true
        if (!map[x][y]) flag = false;
        else {
            for (int d = 0; d < 3; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];
                if (nx < 0 || ny < 0) {
                    flag = false;
                    break;
                } else {
                    if (!map[nx][ny]) { // 만약 터질수 없다면
                        flag = false;
                        break;
                    }
                }
            }
        }
        // 가지치기
        if (flag) {
//            System.out.println("터진다" + num);
            return; // 터질 수 있으면 return
        }

        // 터질 수 없다면 다음 단계
        // 기저 조건
        if(num == N*M-1){
//            System.out.println(num);
            cnt ++;
            return;
        }

        x = (num+1)/M;
        y = (num+1)%M;

//        System.out.println("num+1: "+ (num+1) + " x: " + x + " y: " + y );
        map[x][y] = true;
        subset(num+1);
        map[x][y] = false;
        subset(num+1);
    }
}

 

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

14712번: 넴모넴모 (Easy)