[ 14712 ] [ backtracking ] 넴모넴모(Easy)

https://www.acmicpc.net/problem/14712

14712번: 넴모넴모 (Easy)

---

풀이 과정

---

1. 전체적인 과정은 Recursion으로 진행한다.
2. 현재 위치에 넴모를 넣을수 있으면 넣어보고, 넣을수 없으면 넣지 않고 다음 위치로 이동한다.
3. 이 때, 넴모를 넣었는지 넣지 않았는지 확인하기 위한 격자판을 미리 만들어두고 넴모를 넣었을때 1, 넣지 않았을때 0으로 설정한다.
4. 현재 위치 기준으로 왼쪽, 왼쪽위, 위에 넴모가 있는지 확인하고, 넴모가 모두 있으면 현재 위치엔 넣을수 없으므로 넣지 않고, 넴모가 한군데라도 없다면 현재 위치에 넣을 수 있으므로 넣는다.
5. 넴모를 넣을때마다 정답을 하나씩 증가시켜서 마지막에 전체 경우의 수를 출력시켜 준다.

쉬운 문제인거 같은데 뭔가 많이 헤맸던것 같다.. 넴모의 위치를 처음에는 Set으로 했었는데.. 계속해서 시간초과에 걸려서 행렬로 바꾸었음, 그래도 시간초과에 걸려서 원래 현재 위치 기준으로 삽입할 수 있는지 체크하는걸 함수로 구현하였었는데, 함수에서 일반 비교식으로 바꾸니 시간 초과가 걸리지 않음.

 

---

소스 코드

---

import sys

input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())

block_set = set()
matrix = [[0] * (M+1) for _ in range(N+1)]

def solve(i, j):
    answer = 0
    if j > M:
        i, j = i+1, 1
    if i > N:
        return 0
    
    if matrix[i-1][j] == 0 or matrix[i][j-1] == 0 or matrix[i-1][j-1] == 0:
        matrix[i][j] = 1
        answer += (1 + solve(i, j+1))
        matrix[i][j] = 0
    answer += solve(i, j+1)

    return answer

print(solve(1, 1) + 1)