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

14712_넴모넴모 (Easy) (Python)

0. 출처

• 유형 : 백트래킹 (silver 1)
• 링크 : 14712번: 넴모넴모 (Easy)

1. 기록

• 22/04/04 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2 2

- 예제 출력 1 -
15

- 예제 입력 2 -
2 3

- 예제 출력 2 -
57

- 예제 입력 3 -
3 5

- 예제 출력 3 -
22077

(3) 코드

import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[0] * (m + 1) for _ in range(n + 1)]
answer = 0


def dfs(cnt):
    global answer
    if cnt == n * m:
        answer += 1
        return

    x = cnt // m + 1
    y = cnt % m + 1

    dfs(cnt + 1)
    if graph[x - 1][y] == 0 or graph[x][y - 1] == 0 or graph[x - 1][y - 1] == 0:
        graph[x][y] = 1
        dfs(cnt + 1)
        graph[x][y] = 0


dfs(0)
print(answer)

(4) 정리

문제 가지수가 왜 저렇게 나오나 해서 직접 그려보았다.
넴모넴모가 없는 경우까지 count 해주면 출력값이랑 똑같이 나온다.

힌트를 나중에 봤는데 각 칸 별로 넴모가 있는 경우 없는 경우로 경우의 수를 계산하면
넴모가 4격자를 채우는 경우를 포함한 모든 경우를 좀 더 빨리 구할 수 있긴하다.
문제풀이 방식은 힌트를 기초하여 풀은 방식이다.

풀이 방법을 이해하는데 한참걸렸다.
우선 각 칸을 1로 차례차례 채우며 cnt를 증가시킨다.(넴모를 둔다는 의미)
만약 해당 칸에 넴모를 둬서 2x2 격자넴모가 완성되는 경우는 1을 두지 않고 0으로 남긴채로 cnt를 증가시킨다.
그리고 다시 나머지 칸을 채운다.
전체 격자 수만큼 cnt가 채워진 경우 answer를 1증가시킨다. (answer는 문제 조건에 맞게끔 칸이 채워진 경우를 의미)

# 2 x 3 의 격자의 경우 맨 처음에 이렇게 넴모가 채워진다.
# graph[1][1] 에 넴모(1)를 채우면 문제 조건에 만족하지 못하므로 이 경우는 건너뛰고 cnt만 증가시켜 진행한다.
1 1 1
1 0 1

# 그 다음 이런 식으로 graph[1][2]에 넴모를 제외한 식으로 확인하고
1 1 1
1 0 0

# 그 다음은 이렇게 graph[1][0] 에 넴모를 제외하고 그 뒤에 넴모를 채우는 방식으로
1 1 1
0 1 0

이렇게 해당 칸에 넴모를 넣는 경우와 빼는 경우를 문제에서 주어진 조건에 맞게끔 채우는 경우를 백트래킹 방식으로 반복한다.

(5) 참고

참고 풀이
이해잘되는 풀이