[BOJ][🟡5][백준#23083] 꿀벌 승연이

문제 출처

BAEKJOON Online Judge #23083

문제

이세계의 승연이는 꿀벌이다. 승연이가 사는 벌집은 조금 특이한 구조로 되어있다. 벌집은 (N)행 (M)열의 격자로 이루어져 있고, 각 칸은 정육각형 모양이다. 같은 행에 위치한 두 칸을 비교했을 때, 짝수 번째 열의 칸은 홀수 번째 열의 칸보다 반 칸 아래에 위치해 있다. 아래 그림은 3행 4열의 격자로 이루어진 벌집의 예시이다.

두 육각형 칸이 하나의 변을 공유하고 있다면 서로 인접하다고 한다. 육각형 칸의 각 변에는 인접한 칸으로 이동할 수 있는 문이 있는데, 벌집 내 교통 정리를 위해 각 칸에서는 아래쪽, 오른쪽 위, 오른쪽 아래 칸으로만 이동할 수 있다. 또, 벌집에는 구멍 칸이 있을 수도 있는데, 구멍 칸으로는 이동할 수 없다. 승연이는 최근 꿀벌들 사이에 급속도로 전염되고 있는 변이 바이러스를 피하기 위해 벌집콕 생활을 하고 있다. 심심함이 극에 달한 승연이는 벌집의 (1)행 (1)열 칸에서 (N)행 (M)열 칸까지 바깥으로 나가지 않고 이동하는 경로의 개수가 알고 싶어 졌다. 자가 격리 중인 승연이가 더 이상 답답하지 않도록 경로의 개수를 세서 알려주자!

입력

첫째 줄에 (N), (M)이 공백으로 구분되어 주어진다. 다음 줄에는 구멍 칸의 개수 (K)가 주어진다. 이어서 (K)개 줄에 구멍 칸의 정보 (x_i), (y_i)가 공백으로 구분되어 주어진다. 이는 (i)번째 구멍 칸이 (x_i)행 (y_i)열에 존재함을 뜻한다. 모든 구멍 칸의 위치는 서로 다르다. (1)행 (1)열 칸 또는 (N)행 (M)열 칸이 구멍인 경우는 없음이 보장된다.

출력

벌집의 (1)행 (1)열 칸에서 (N)행 (M)열 칸으로 이동하는 경로의 개수를 (10^9+7)로 나눈 나머지를 출력한다.

제한

2 ≤ (N) ≤ 1,000 2 ≤ (M) ≤ 1,000 0 ≤ (K) ≤ min((NM) - 2, 104) 1 ≤ (x_i) ≤ (N) 1 ≤ (y_i) ≤ (M)

예제

입력

3 4
1
2 3

출력

20

My Sol

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)

def main():
    def make_holes():
        K = int(input())
        for _ in range(K):
            i, j = map(int, input().split())
            dp[i][j] = 0

    def find_dp(i, j):
        if dp[i][j] != -1: return dp[i][j]
        val = find_dp(i-1, j)+find_dp(i, j-1)
        val += find_dp(i-1, j-1) if j%2 else find_dp(i+1, j-1)
        dp[i][j] = int(val%X)
        return dp[i][j]

    X = 1e9+7
    I, J = map(int, input().split())
    dp = [[-1]*(J+1) for _ in range(I+2)]
    dp[1][1] = 1
    for i in range(I+1):
        dp[i][0] = 0
    for j in range(J+1):
        dp[0][j] = 0
        dp[I+1][j] = 0
    make_holes()
    return find_dp(I, J)

print(main())

DP를 사용하는 문제였다. 골드5 DP문제치고는 시간초과 이슈로 최적화를 최대한 한 뒤에야 풀 수 있었던 까다로운 문제였다.

1. 기본적으로 dp 2차원 배열은 0으로 초기화하는 편인데, 경계값에서 바로 0을 return하는 것을 범위 조건이 아닌 초기화 값이 아닌 것으로 하기 위해 -1로 초기화하고 경계를 0으로 초기화해 종료 조건으로 하였다.
2. (1, 1) 좌표를 1로 두고, dp는 (I, J)부터 조회해서 줄여나간다. 이를 find_dp 함수로 작성해서 memoization하였다.
3. dp[i][j]에 값이 초기값인 -1이 아니라면 바로 return하고 아니라면 해당 좌표까지 도달하기 위한 경우의 수 dp[i-1][j], dp[i][j-1]를 더해준다. 여기에 벌집 모양 계산의 관건인 j열의 홀짝 여부를 확인하여 dp[i-1][j-1] 또는 dp[i+1][j-1]를 더해준 뒤 dp 배열에 memoization한 뒤 반환한다.

결과

맞았습니다!!