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

14712번 - 넴모넴모 (Easy)

문제 이해

격자판에 넴모를 놓는데, 2*2로 놓게 될 경우 4개의 넴모가 터지게 된다.
N*M의 칸에 1을 채우는데, 2*2로 놓하지는 경우가 없으면 된다는 것이다.
백트래킹, DP로 풀 수 있을 것이라 생각했고, 문제에 (Easy)가 붙은 것으로 보아 아마 (Medium) 또는 (Hard)문제에서 DP 풀이가 요구될 것이라 생각했다.
아니나 다를까 14700번 - 넴모넴모 (Hard) 문제는 제한으로 볼 때 DP로 풀어야 풀리는 문제로 보인다.

접근

백트래킹을 통해 해결해 보기로 했고, 지금 보고있는 칸에 넴모를 놓았을 때 2*2가 되면 안된다.
바로 왼쪽, 왼쪽위, 위의 좌표가 모두 채워져 있다면 놓지 못하는 것이기에 해당 조건에 맞추어 백트래킹 코드를 작성했다.
경계조건을 고려하지 않기 위해 1-base로 좌표를 설정했다. (가장 왼쪽 위 좌표가 1, 1)

정답 코드

import sys
input = sys.stdin.readline
def getInts(): return map(int, input().split())


def dfs(k):
    global cnt
    if k == N * M:
        cnt += 1
        return
    y, x = k//M + 1, k % M + 1

    # 넴모 안놓는 경우
    dfs(k+1)

    # 넴모 놓는 경우
    # 지금 놓은 칸이 2*2 넴모를 구성해 터지지 않는 경우만 놓기
    if not (board[y-1][x]*board[y][x-1]*board[y-1][x-1]):
        board[y][x] = 1
        dfs(k+1)
        board[y][x] = 0


N, M = getInts()
board = [[0]*(M+1) for _ in range(N+1)]
cnt = 0
dfs(0)
print(cnt)

# python 3로 제출시 시간초과, pypy3로 제출시 맞았습니다를 받는다.