14712번: 넴모넴모 (Easy)
네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의
www.acmicpc.net
문제
네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 비어 있는 칸을 임의로 골라 “넴모”를 하나 올려놓거나, “넴모”가 올라간 칸 네 개가 2 × 2 사각형을 이루는 부분을 찾아 그 위에 있는 “넴모”들을 모두 없애는 것을 질릴 때까지 반복하면 된다.
하지만 안타깝게도 게임은 정말 재미가 없었고, 네모는 아주 빨리 질려 버리고 말았다. 실망한 네모는 게임을 적당히 플레이하다가, “넴모”를 없애고 싶은데 격자판 위에 없앨 수 있는 “넴모”가 없으면 게임을 그만두기로 했다. 네모가 게임을 그만두었을 때 나올 수 있는 “넴모”의 배치의 가짓수를 구하여라.
입력
첫 번째 줄에 격자판의 행의 개수 N, 열의 개수 M(1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25)이 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 출력한다.
코드
n, m = map(int, input().split())
arr = [[False for _ in range(m+1)] for _ in range(n+1)]
ans = 0
def dfs(r,c):
global ans
if r == n + 1 and c == 1:
ans += 1
return
if c == m:
nr = r + 1
nc = 1
else:
nr = r
nc = c + 1
# 이번 칸에 넴모를 놔도 2X2가 되지 않는 경우 넴모 놓기
if not (arr[r-1][c-1] and arr[r-1][c] and arr[r][c-1]):
arr[r][c] = True
dfs(nr, nc)
arr[r][c] = False
# 이번 칸에 넴모 안 놓고 지나가기
dfs(nr, nc)
dfs(1, 1)
print(ans)
Python3로는 시간 초과가 발생하는데 PyPy3로는 통과한다.
arr의 크기를 (n+1)행 (m+1)열로 한 것은 코드 17줄에서 넴모를 놔도 2X2가 되는지 판단할 때 편하게 하려고 그런 것이다.
그러니까 사실상 우리가 봐야하는 arr의 범위는 1~n행 1~m열이다.
예를 들어 입력으로 2 3이 들어 온다면 다음과 같은 arr을 생각하면 된다. 보라색으로 표시된 부분을 보는 것이다. 흰색 부분은 항상 False이므로 저 부분이 포함된다면 2X2가 될 수 없다.
'문제풀이 > 백트래킹' 카테고리의 다른 글
[Python/파이썬] 백준 16987번 계란으로 계란치기 (0) | 2023.05.05 |
---|---|
[Python/파이썬] 백준 14888번 연산자 끼워넣기 (0) | 2023.05.04 |
[Python/파이썬] 백준 10971번 외판원 순회 2 (1) | 2023.03.11 |
[Python/파이썬] 백준 15655번 N과 M (6) (0) | 2023.03.10 |
[Python/파이썬] 백준 15654번 N과 M (5) (0) | 2023.03.10 |