[백준] 넴모넴모(14712번)

[출처] https://www.acmicpc.net/

문제

네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 비어 있는 칸을 임의로 골라 “넴모”를 하나 올려놓거나, “넴모”가 올라간 칸 네 개가 2 × 2 사각형을 이루는 부분을 찾아 그 위에 있는 “넴모”들을 모두 없애는 것을 질릴 때까지 반복하면 된다.

하지만 안타깝게도 게임은 정말 재미가 없었고, 네모는 아주 빨리 질려 버리고 말았다. 실망한 네모는 게임을 적당히 플레이하다가, “넴모”를 없애고 싶은데 격자판 위에 없앨 수 있는 “넴모”가 없으면 게임을 그만두기로 했다. 네모가 게임을 그만두었을 때 나올 수 있는 “넴모”의 배치의 가짓수를 구하여라.

입력

첫 번째 줄에 격자판의 행의 개수 N, 열의 개수 M(1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25)이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 출력한다.

예제 입출력

접근 및 코드

N-Queen과 유사한 백트래킹 문제이다.
게임판위에 네모를 올릴수 있는데, 네모가 2X2사각형을 이루지 않게 배치할수 있는 경우의 수를 구하는 문제이다.

접근은 심플하다.
백트래킹을 이용해서 풀면 된다.
네모를 하나씩 놓으면서, 2X2가 만들어지지 않았다면, 다시 자기 자신을 호출해서 네모가 놓인 게임판에서 또 네모를 하나씩 올려놓으면 된다.

이렇게 구할수 있는 경우의 수를 전부 구해주면 된다

네모가 2X2가 되었는지 확인할때, 처음에는 0,0부터 네모를 놓고, 오른쪽, 아래, 오른쪽 아래 대각선을 확인하는 방식으로 진행했다.

그런데 이렇게 하면 문제점이, 처음 0,0에 놓았을때, 오른쪽, 아래, 오른쪽 아래 대각선 이 세군데는 놓여있지 않아서 네모를 놓게 되면, (1,0),(0,1),(0,0)에 네모를 놓고 똑같이 세군데를 확인하면 마찬가지로 2X2가 되지 않는다.

하지만 확인하지 않았을 뿐이지 (0,0),(1,0),(0,1),(0,0) 이 네군데에는 네모가 놓여서 2X2가 만들어지게 된다.

따라서 오른쪽, 아래, 오른쪽 아래 대각선 이 네군데가 아닌, 왼쪽, 위, 왼쪽위 대각선 을 확인하는 식으로 해야, 정확하게 체크가 가능해진다.

(그림처럼 탐색해야 제대로 체크가 가능하다.)

아래는 코드이다

import sys

#행 개수, 열개수
n,m = map(int,sys.stdin.readline().split())

# 넴모가 올라갈 격자 판
graph = [[0 for _ in range(m)] for _ in range(n)]


#격자판 탐색 - node 는 넴모를 놓는 위치
def dfs(x,y:list)->int:
    #경우의 수 세기
    count = 0 
    #열이 격자판을 넘어가면 행을 하나 증가
    if y >= m:
        x = x+1
        y = 0
    #행을 증가했는데 격자판을 넘어가면 전부 탐색한 것임 - 탐색 끝
    if x >= n:
        return 0
    
    #넴모를 놓아도 터트릴수 없는 위치지면 놓고 다음 경우 탐색 - 3개중 한칸이라도 0이면 놓을수 있음
    if graph[x][y-1] ==0 or graph[x-1][y-1] == 0 or graph[x-1][y] == 0:
        #넴모를 놓음
        graph[x][y] = 1
        #네모를 놓은 상태에서 재귀를 이용해서 다음 경우 탐색하고, 그 결과에 현재 놓은 결과를 더해서 넣어줌
        count+=dfs(x,y+1)+ 1

        #다음 탐색을 위해서 놓았던 네모를 다시 빈칸으로 돌려놓음
        graph[x][y] = 0

    count += dfs(x,y+1)

    return count

print(dfs(0,0)+1)

결과

파이썬의 경우, pypy3로 제출하지 않으면 통과할수 없었다.