[백준] 23083번 : 꿀벌 승연이

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

23083번: 꿀벌 승연이

(1,1) 위치에서 N,M 위치까지 갈 수 있는 경우의 수를 모두 구하는 문제이다. 해당 문제는 깊이우선탐색 으로 이미 방문했던 곳을 다시 방문하지 않기 위하여 dp 테이블을 생성하여 메모리제이션 한다.  점화식은 짝수 일때와 홀수 일때 각각 다르다. 움직 일 수 있는 조건을 잘 나누어서 풀면 된다.

 

import sys
sys.setrecursionlimit(10**9)
N, M = map(int, input().split()) # N은 세로, M은 가로
RESULT = int(1e9 + 7)
table = [[1 for _ in range(M)] for _ in range(N)]
visited = [[-1 for _ in range(M)] for _ in range(N)]
move = [(1,0), (-1,1), (0,1)] # 홀수일때
move2 = [(1,0), (0,1), (1,1)] # 홀수일때
K = int(input()) # 구멍칸의 개수

for _ in range(K):
    a, b = map(int, input().split())
    table[a-1][b-1] = 0

def dfs(i,j):
    if i == N-1 and j == M-1:
        visited[i][j] = 1
        return 1
     
    if visited[i][j] != -1:
        return visited[i][j]
    
    visited[i][j] = 0

    for k in range(3):
        newy, newx  = 0 ,0
        if j % 2 == 1: # 홀수일때
            newy , newx = move2[k]
        else: # 짝수일때
            newy , newx = move[k]
        dy = i + newy
        dx = j + newx
        if N > dy >=0 and M > dx >=0 and table[dy][dx] == 1:
            visited[i][j] += (dfs(dy,dx) % RESULT)

    return visited[i][j]


dfs(0,0)
print(visited[0][0] % RESULT)