[알고리즘] 넴모넴모
https://www.acmicpc.net/problem/14712
문제
네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 비어 있는 칸을 임의로 골라 “넴모”를 하나 올려놓거나, “넴모”가 올라간 칸 네 개가 2 × 2 사각형을 이루는 부분을 찾아 그 위에 있는 “넴모”들을 모두 없애는 것을 질릴 때까지 반복하면 된다.
하지만 안타깝게도 게임은 정말 재미가 없었고, 네모는 아주 빨리 질려 버리고 말았다. 실망한 네모는 게임을 적당히 플레이하다가, “넴모”를 없애고 싶은데 격자판 위에 없앨 수 있는 “넴모”가 없으면 게임을 그만두기로 했다. 네모가 게임을 그만두었을 때 나올 수 있는 “넴모”의 배치의 가짓수를 구하여라.
입력
첫 번째 줄에 격자판의 행의 개수 N, 열의 개수 M(1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25)이 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 출력한다.
import sys
def dfs(cnt):
global answer
# 모든 칸을 확인한 경우 정답 1개 카운트
if cnt == Y * X:
answer += 1
return
# 현재 좌표
y, x = cnt // X, cnt % X
# 좌표가 범위내에 있는경우
# 상, 좌, 상좌 위치에 네모가 있으면 바로 다음 칸확인
if (0 < y < Y and 0 < x < X) and (arr[y - 1][x] and arr[y][x - 1] and arr[y - 1][x - 1]):
dfs(cnt + 1)
# 네모가 없는 경우
else:
# 네모 추가한 경우 확인
arr[y][x] = 1
dfs(cnt + 1)
# 추가하지 않은 경우 확인
arr[y][x] = 0
dfs(cnt + 1)
Y, X = map(int, sys.stdin.readline().split())
arr = [[0] * X for _ in range(Y)]
answer = 0
dfs(0)
print(answer)
Author And Source
이 문제에 관하여([알고리즘] 넴모넴모), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsw4215/알고리즘-넴모넴모저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)