[백준] 14712 넴모넴모 (Javascript)

문제

BOJ14712_넴모넴모

요구사항

넴모가 $2 \times 2$가 되지 않는 배치의 가지 수를 구하시오

접근법

• 모든 경우의 수를 확인한다면 시간이 얼마나 걸릴까?
• 매 칸마다 넴모를 놓는 경우, 놓지 않는 경우가 있으므로 시간복잡도는 $O(2^{NM})$이다.
• $N\times M$은 최대 $25$라고 문제의 입력 조건에 나와있다.
• $O(2^{25}) = 33,554,432$ 이므로 해볼만 하다.

풀이

1. arr[N-1][M-1] 까지 넴모를 다 채우고 나서 $2 \times 2$ 넴모가 있는지 확인하는 방법

// 넴모가 2x2 사각형을 이루지 않는 모든 배치의 가짓수 구하기
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, M] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const arr = Array(N * M).fill(0);
let answer = 0;

function dfs(cur) {
    if (cur === N * M) {
        for (let i = 0; i < N * M; i++) {
            // 오른쪽 끝일 경우
            if (i % M === M - 1) continue;
            // 마지막 줄일 경우
            if (i === (N - 1) * M) break;
            // 2 x 2 넴모가 있을 경우
            if (arr[i] && arr[i + 1] && arr[i + M] && arr[i + M + 1]) return;
        }

        answer++;
        return;
    }

    arr[cur] = 1;
    dfs(cur + 1);

    arr[cur] = 0;
    dfs(cur + 1);
}

dfs(0);

console.log(answer);

2. 각 칸을 넴모로 채울 때마다 $2 \times 2$ 넴모가 생겼는지 확인하는 방법

// 넴모가 2x2 사각형을 이루지 않는 모든 배치의 가짓수 구하기
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, M] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const arr = Array(N * M).fill(0);
let answer = 0;

function dfs(cur) {
    const prev = cur - 1;
    // 2 x 2 인가?
    const isRect = arr[prev] && arr[prev - 1] && arr[prev - M] && arr[prev - (M + 1)];
    // 가장자리인가?
    const isEdge = prev % M === 0 || prev < M;
    // 가장 자리가 아니고 넴모가 2*2라면 return
    if (!isEdge && isRect) return;
    if (cur === N * M) {
        answer++;
        return;
    }

    // 현재 위치에 넴모 넣기
    arr[cur] = 1;
    dfs(cur + 1);

    // 현재 위치의 넴모 제거
    arr[cur] = 0;
    dfs(cur + 1);
}

dfs(0);

console.log(answer);

두 풀이 전부 1차원 배열을 사용했는데, 이유는 지역성의 원리 때문이다. 2차원 배열은 배열의 원소가 배열이고, 이때의 각 배열들은 메모리 상에서 연속된 공간에 저장되는 것이 아니라 불규칙적으로 저장된다.

CPU는 가까운 미래에 다시 사용할 것 같은 데이터를 예측해서 이를 캐시에 저장함으로써 수행속도를 단축시킨다. 이때 예측 정확도를 높이기 위해 사용하는 개념이 지역성의 원리이고, 지역성의 원리중에는 공간 지역성이라는 것이 있다.

공간 지역성은 메모리 상에서 서로 인접한 위치에 있는 데이터를 다시 참조하는 경향으로써, 간단히 말하면 메모리상에서 인접해 있는 데이터를 캐시에 저장한다는 의미다.

따라서 2차원 배열에서 행 이동은 메모리 상에서 서로 떨어져있는 데이터에 접근하는 것이기 때문에 캐시에 저장될 확률이 낮으므로 열 이동보다 동작 속도가 느리다.

따라서 2차원 배열 대신 1차원 배열을 사용한 것이다.

하지만, 배열의 높이가 그렇게 크지 않다면 사실 큰 속도 차이는 없다. 해당 문제에서 배열의 높이는 최대라고 해봤자 $25$이므로 속도 차이는 크지 않다.

아래는 1번 풀이를 2차원 배열을 사용해서 푼 코드다.

// 넴모가 2x2 사각형을 이루지 않는 모든 배치의 가짓수 구하기
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, M] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const arr = Array.from(Array(N), () => Array(M).fill(0));
let answer = 0;

function dfs(x, y) {
    if (y === N) {
        for (let i = 0; i < N - 1; i++) {
            for (let j = 0; j < M - 1; j++) {
                // 2 x 2 넴모가 있을 경우
                if (arr[i][j] && arr[i][j + 1] && arr[i + 1][j] && arr[i + 1][j + 1]) return;
            }
        }

        answer++;
        return;
    }
	
  	// 줄이 바뀌는 경우 고려
    const ny = x % M === M - 1 ? y + 1 : y; 
    const nx = x % M === M - 1 ? 0 : x + 1;

    arr[y][x] = 1;
    dfs(nx, ny);

    arr[y][x] = 0;
    dfs(nx, ny);
}

dfs(0, 0);

console.log(answer);

속도는 조금 더 느리긴 하지만 큰 차이는 없다.

아래처럼 i와 j를 바꿔서 행이동 횟수를 더 늘리면 좀 더 느려지는 모습을 확인할 수 있다.

// 넴모가 2x2 사각형을 이루지 않는 모든 배치의 가짓수 구하기
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [N, M] = require('fs').readFileSync(filePath).toString().trim().split(' ').map(Number);
const arr = Array.from(Array(N), () => Array(M).fill(0));
let answer = 0;

function dfs(x, y) {
    if (y === N) {
        for (let i = 0; i < M - 1; i++) {
            for (let j = 0; j < N - 1; j++) {
                // 2 x 2 넴모가 있을 경우
                if (arr[j][i] && arr[j][i + 1] && arr[j + 1][i] && arr[j + 1][i + 1]) return;
            }
        }

        answer++;
        return;
    }

    const ny = x === M - 1 ? y + 1 : y;
    const nx = x === M - 1 ? 0 : x + 1;

    arr[y][x] = 1;
    dfs(nx, ny);

    arr[y][x] = 0;
    dfs(nx, ny);
}

dfs(0, 0);

console.log(answer);