[BOJ] 14712 - 넴모넴모 (Easy) (Python, JavaScript)

 

 

아이디어

 

DFS로 넴모들을 격자판에 배치하고 2×2 사각형 칸에 모두 넴모가 배치된 경우는 더 탐색하지 않는다.

 

 

풀이 #1 (Python)

 

N이나 M이 1인 경우 2×2 사각형 칸이 존재할 수 없으므로 격자판에서 넴모를 배치하는 모든 경우의 수를 출력한다.

 

그렇지 않으면 넴모 배치를 위한 2차원 리스트 visited를 만드는데, 인덱스 에러 방지를 위해 행과 열 크기를 1씩 늘린다.

(1, 1)을 시작점으로 하여 방문 표시 후 함수 dfs를 호출하고, 시작점 방문 표시를 지우고 다시 함수 dfs를 호출한다.

 

함수 dfs에서는 현재 칸을 기준으로 현재 칸, 위쪽 칸, 왼쪽 칸, 좌상단 칸에 모두 넴모가 배치되면 백트래킹으로 종료한다.

격자판 한 행씩 왼쪽에서 오른쪽으로 넴모들을 배치해 나가고, 종료 없이 else문을 만나면 결과값 res를 1 증가시킨다.

 

# Python 3 기준 시간 초과, PyPy3 통과 코드
def dfs(i, j):
    global res
    if visited[i][j] and visited[i][j-1] and visited[i-1][j] and visited[i-1][j-1]:
        return
    if j < M:
        visited[i][j+1] = 1
        dfs(i, j+1)
        visited[i][j+1] = 0
        dfs(i, j+1)
    elif i < N:
        visited[i+1][1] = 1
        dfs(i+1, 1)
        visited[i+1][1] = 0
        dfs(i+1, 1)
    else:
        res += 1

N, M = map(int, input().split())
if N == 1 or M == 1:
    print(2**(N*M))
else:
    res = 0
    visited = [[0]*(M+1) for _ in range(N+1)]
    visited[1][1] = 1
    dfs(1, 1)
    visited[1][1] = 0
    dfs(1, 1)
    print(res)

 

 

 

풀이 #2 (Python)

 

N과 M의 조합이 많지 않아 하드코딩으로 코드를 작성할 수도 있다.

N×M 격자판의 배치 가짓수는 M×N 격자판의 배치 가짓수와 같으므로 N이 M보다 작거나 같은 경우의 가짓수만 저장한다.

 

res = dict({(2, 2): 15, (2, 3): 57, (2, 4): 216, (2, 5): 819,
            (2, 6): 3105, (2, 7): 11772, (2, 8): 44631, (2, 9): 169209,
            (2, 10): 641520, (2, 11): 2432187, (2, 12): 9221121,
            (3, 3): 417, (3, 4): 3032, (3, 5): 22077, (3, 6): 160697,
            (3, 7): 1169792, (3, 8): 8515337, (4, 4): 42176, (4, 5): 587920,
            (4, 6): 8191392, (5, 5): 15701273})

N, M = map(int, input().split())
if N == 1 or M == 1:
    print(2**(N*M))
else:
    if N > M:
        N, M = M, N
    print(res.get((N, M)))

 

 

 

풀이 #3 (JavaScript)

 

풀이 #1과 같은 방식으로 동작하며, 결과값을 저장하는 변수 res를 else문 내에 정의하면 에러가 발생한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

function dfs(i, j) {
    if (visited[i][j] && visited[i][j-1] && visited[i-1][j] && visited[i-1][j-1]) return;
    if (j < M) {
        visited[i][j+1] = 1;
        dfs(i, j+1);
        visited[i][j+1] = 0;
        dfs(i, j+1);
    }
    else if (i < N) {
        visited[i+1][1] = 1;
        dfs(i+1, 1);
        visited[i+1][1] = 0;
        dfs(i+1, 1);
    }
    else res += 1;
}

const [N, M] = input[0].split(' ').map(Number);
let res = 0;
if (N == 1 || M == 1) console.log(2**(N*M));
else {
    visited = Array.from(Array(N+1), () => Array(M+1).fill(0));
    visited[1][1] = 1;
    dfs(1, 1);
    visited[1][1] = 0;
    dfs(1, 1);
    console.log(res);
}