[백준] 14712. 넴모넴모 (백트래킹/Java)

[백준] 14712. 넴모넴모 (Easy)

 

📌 풀이 과정

넴모넴모

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

 

각 칸을 순차적으로 선택하거나 선택하지 않으면서 모든 경우의 수를 탐색한다.

즉, 각 칸에 두가지 경우가 존재한다.

1. 넴모를 놓는 경우 (해당 칸 선택 O)

2. 넴모를 놓지 않는 경우 (해당 칸 선택 X)

 

(x, y) 좌표 탐색 중일 때, 이미 선택된 칸(x,y 좌표의 좌상단 3칸)들이

• 2 × 2 사각형이 만들어지는 경우 ➡️ 해당 탐색 칸은 선택하지 않는다.
• 아닌 경우 ➡️ 해당 칸을 선택한 경우와 선택하지 않은 경우 모두에 대해 탐색한다.

모든 칸을 탐색했을 때 (cnt == N * M), 경우의 수를 증가키고 종료한다.

 

💡 1차원 인덱스 관리

분명 이 문제는 N*M 크기의 2차원 인접행렬로 주어졌는데

1차원 인덱스로 선택 여부를 관리하는 이유가 무엇일까?

 

cnt라는 하나의 변수만으로 탐색 순서를 일관되게 유지할 수 있다.

즉, cnt가 0부터 N * M까지 차례대로 증가하면서 배열의 모든 칸을 순차적으로 탐색할 수 있다.

int index = row * 5 + col;

 

 

x = cnt / M + 1 : 현재 cnt가 몇 번째 행에 있는지 계산

y = cnt % M + 1 : 현재 cnt가 몇 번째 열에 있는지 계산

이런 방식으로 2차원 좌표를 하나의 인덱스로 변환해 관리할 수 있다.

 

 

 

조합으로 풀릴까?

 

안풀린다.

2×2 격자판에 2×2 사각형을 이루지 않도록 “넴모”들을 배치하는 방법은 모든 경우(2^4 = 16) 중 네 칸 모두에 “넴모”가 올라가 있는 경우를 제외한 15가지가 있다.

문제에서 이렇게 힌트가 주어졌다.

 

조합으로 격자에서 가능한 모든 2x2 직사각형을 선택한 후

나머지 칸들에 대해 선택하거나 선택하지 않는 경우의 수 2^N*M - 4를 구한다.

이렇게 구한 경우의 수가 네 칸 모두에 넴모가 올라가 있는 경우가 된다.

따라서, 전체 경우(2^N*M)에서 2*2 직사각형을 포함하는 경우를 빼면 정답이 나올 것이라는 확신을 했다.

 

하지만, 직사각형을 포함한 나머지 칸들을 다 선택하는 경우, 다 선택하지 않는 경우가 중복되기 때문에

추가적으로 중복 처리를 해줘야하지만 구현하기 까다로웠다.

✨ 제출 코드

첫번째 코드

메모리 : 16852 KB

시간 : 1492 ms

 

처음 제출한 코드에서는 모든 선택의 순간마다

isSquare()를 호출해 2 * 2 직사각형이 성립되는지 반복적으로 확인하고 있기 때문에 비효율적이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, M, answer = 0;
    static boolean[][] picked;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 행
        M = Integer.parseInt(st.nextToken()); // 열
        picked = new boolean[N][M];

        batch(0, 0);

        System.out.println(answer);

    }

    private static void batch(int start, int cnt){

        if(!isSquare(cnt)) answer++;

        if(cnt == N * M) return;

        for(int i = start; i < N * M; i++){
            int x = i / M; int y = i % M;

            if(!picked[x][y]){
                picked[x][y] = true;
                batch(i + 1, cnt + 1);
                picked[x][y] = false;
            }
        }
    }

    private static boolean isSquare(int cnt){
        if(cnt < 4) return false;

        for(int i = 0; i < N-1; i++){
            for(int j = 0; j < M-1; j++){
                if(picked[i][j] && picked[i][j+1] &&
                    picked[i+1][j] && picked[i+1][j+1]){
                    return true;
                }
            }
        }
        return false;
    }

}

 

두번째 코드

메모리 : 16216 KB

시간 : 404 ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N, M, answer = 0;
    static boolean[][] picked;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 행
        M = Integer.parseInt(st.nextToken()); // 열
        picked = new boolean[N+1][M+1];

        batch(0);

        System.out.println(answer);

    }

    private static void batch(int cnt){

        if(cnt == N * M) {
            answer++;
            return;
        }

        int x = cnt / M + 1;
        int y = cnt % M + 1;

        // 2*2 직사각형 만들 수 있는 경우 (x, y) 좌표는 선택하지 않는다.
        if(picked[x-1][y] && picked[x][y-1] && picked[x-1][y-1]){
            batch(cnt + 1);
        }
        else{
            picked[x][y] = true;
            batch(cnt + 1);
            picked[x][y] = false;
            batch(cnt + 1);
        }
    }

}