[Java] 백준 2411 아이템 먹기

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

난이도

골드 4

문제

N×M 모양의 맵에 아이템과 장애물이 있다. 이때 맵의 왼쪽 아래에서 출발하여 오른쪽 위로 가려고 하는데, 중간에 모든 아이템을 먹으려고 한다. 이동할 때에는 오른쪽이나 위쪽으로만 이동할 수 있다. 또, 장애물이 있는 곳으로는 지날 수 없다.

이때, 이동하는 경로의 개수가 총 몇 개인지 알아내는 프로그램을 작성하시오. 위의 예에서 ◎은 장애물, ☆는 아이템이다. 이때 경우의 수는 4 가지가 된다.

입력

첫째 줄에 N, M(1 ≤ N, M ≤ 100), A(1 ≤ A), B(0 ≤ B)가 주어진다. A는 아이템의 개수이고, B는 장애물의 개수이다. 다음 A개의 줄에는 아이템의 위치, B개의 줄에는 장애물의 위치가 주어진다. 위치를 나타낼 때에는 왼쪽 아래가 (1, 1)이 되고 오른쪽 위가 (N, M)이 된다.

출력

첫째 줄에 경우의 수를 출력한다. 이 값은 int 범위이다.

코드

import java.util.*;
import java.io.*;

class Main {

    static int N, M, A, B;
    static boolean[][] blocked = new boolean[101][101];
    static List<int[]> items = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        for(int i = 0; i < A; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            items.add(new int[]{x, y});
        }

        for(int i = 0; i < B; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            blocked[x][y] = true;
        }

        items.add(new int[]{0, 0});
        items.add(new int[]{N-1, M-1});
        items.sort((a, b) ->{
            if(a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

        long ans = 1;
        for(int i = 0; i < items.size() - 1; i++){
            int[] start = items.get(i);
            int[] end = items.get(i + 1);
            ans *= findPaths(start[0], start[1], end[0], end[1]);
        }

        System.out.println(ans);
    }

    public static int findPaths(int sx, int sy, int ex, int ey){
        if(sx > ex || sy > ey) return 0;

        int[][] dp = new int[N][M];
        if (blocked[sx][sy]) return 0;
        dp[sx][sy] = 1;

        for(int i = sx; i <= ex; i++){
            for(int j = sy; j <= ey; j++){
                if(blocked[i][j]){
                    dp[i][j] = 0;
                    continue;
                }
                if(i > sx) dp[i][j] += dp[i-1][j];
                if(j > sy) dp[i][j] += dp[i][j-1];
            }
        }

        return dp[ex][ey];
    }
}