[BOJ] 23083. 꿀벌 승연이 (🥇, DP)

🔗

배열의 최대 크기가 백만이기 때문에 모든 경우의 수를 dfs로 탐색할 수는 없다. 대신 특정 칸에 도달하는 경우의 수는 항상 변함이 없기 때문에 이 경우의 수들을 누적해서 최종 값을 구할 수 있다.

각 경로에 도달하는 경우의 수 누적해서 구하기

우선 1행 1열을 보면 1행 2열과 2행 1열에 갈 수 있다. 1행 1열에 도달하는 방법은 1가지 이므로 나머지 두 칸 역시 도달하는 방법은 1가지이다.

2행 1열은 1행 2열, 3행 1열, 2행 2열에 도달할 수 있는데 이때 1행 2열은 이미 1행 1열을 통해 바로 갈 수 있는 경우의 수 1가지가 존재했으므로 여기에 추가적으로 2행 1열까지 도달할 수 있는 경우의 수를 더해주면 된다. 1행 2열에 도달할 수 있는 방법은 최종적으로 2가지가 된다.

3행 1열 역시 마찬가지이다. 이때 행이 우선되는 이유는 아래 행으로 내려간 값들은 다시 오른쪽 열로 이동할 수 있기 때문이다. 반대로 오른쪽 열로 한 번 이동한 값은 왼쪽 열로 다시 되돌아올 수 없다. 누적되지 않는다. 여기서는 누적될 수 있는 방향으로만 이동해야 한다.

이때 이동방향 이외에도 짝수열, 홀수열 여부에 따라 이동할 수 있는 방향이 다르다는 점을 고려해야 한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static int rem = 1_000_000_000 + 7;
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        
        int[][] arr = new int[N][M];
        int K = sc.nextInt();
        int x; int y;
        for (int i = 0; i < K; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            arr[x-1][y-1] = -1;
        }

        arr[0][0] = 1;
        int nextRow; int nextCol;
        int[][][] dir = new int[][][] {
            {{-1, 1}, {0, 1}, {1, 0}}, 
            {{0, 1}, {1, 1}, {1, 0}}
        };
        
        for (int col = 0; col < M; col++) {
            for (int row = 0; row < N; row++) {
                if (arr[row][col] == -1) continue;

                for (int k = 0; k < 3; k++) {
                    nextRow = row + dir[col%2][k][0];
                    nextCol = col + dir[col%2][k][1];

                    if (nextRow < 0 || nextCol < 0 || nextRow >= N || nextCol >= M || arr[nextRow][nextCol] == -1) continue;
                    arr[nextRow][nextCol] += arr[row][col];
                    arr[nextRow][nextCol] %= rem;
                }
            }
        }

        System.out.println(arr[N-1][M-1] % rem);
        
    }
}