[BOJ] 14712. 넴모넴모 (Easy) (🥇, 백트래킹)

🔗

풀이

모든 칸은 넴모를 놓거나 놓지 않는 2가지 경우가 존재할 수 있다. 2x2 형태의 넴모가 이뤄지지 않도록 위쪽 왼쪽부터 오른쪽 아래쪽까지 차례대로 탐색한다. 도중에 2x2를 이루게 된다면 백트래킹으로 탐색을 중단한다.

# 넴모넴모 (Easy)

def possible(r, c):
    count = 0
    if r>0 and arr[r-1][c]:
        count += 1
    if c>0 and arr[r][c-1]:
        count += 1
    if r>0 and c>0 and arr[r-1][c-1]:
        count += 1
    return count != 3

def nemo(i):
    global nemo, result
    if i == n*m:
        result += 1
        return 
    
    r, c = divmod(i, m)
    if possible(r, c):
        arr[r][c] = 1
        nemo(i+1)
        arr[r][c] = 0
    nemo(i+1)

n, m = map(int, input().split())
arr = [[0]*m for _ in range(n)]

result = 0
nemo(0)
print(result)