[Java] 백준 2411 - 아이템 먹기

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

---

풀이

아이템을 체크포인트 삼아 문제를 여러 작은 행렬 경로 문제로 나누기!

예를 들어, 예제 입력 1의 경우에는 아래와 같이 구역을 나눠서 각 구역마다 행렬 경로 문제 적용 

 

구역을 나눈다고 표현했는데 사실 아이템을 왼쪽 아래 (1, 1) 와 가까운 기준으로 정렬하고 차례대로 먹으로 가면 됨

추가로, 시작점 (1, 1)과 도착점 (N, M)에도 아이템이 있다고 생각하면 구현 때 편함

 

---

코드

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

public class Main {
	public static class Point {
		public int row, col;

		public Point(int r, int c) {
			row = r;
			col = c;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int[][] dp = new int[N + 1][M + 1];
		Point[] points = new Point[A + 2];
		boolean[][] obs = new boolean[N + 1][M + 1];

		points[0] = new Point(1, 1);
		points[A + 1] = new Point(N, M);
		for (int i = 1; i <= A; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			points[i] = new Point(r, c);
		}

		for (int i = 0; i < B; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			obs[r][c] = true;
		}
		br.close();

		Arrays.sort(points, (o1, o2) -> {
			if (o1.row == o2.row) {
				return o1.col - o2.col;
			}
			return o1.row - o2.row;
		});

		if (obs[1][1]) {
			System.out.println(0);
			return;
		}
		dp[1][1] = 1;

		for (int i = 1; i <= A + 1; i++) {
			Point start = points[i - 1];
			Point end = points[i];

			if (dp[start.row][start.col] < 1) {
				System.out.println(0);
				return;
			}

			for (int r = start.row + 1; r <= end.row; r++) {
				if (obs[r][start.col]) {
					break;
				}
				dp[r][points[i - 1].col] = dp[r - 1][points[i - 1].col];
			}

			for (int c = start.col + 1; c <= end.col; c++) {
				if (obs[start.row][c]) {
					break;
				}
				dp[start.row][c] = dp[start.row][c - 1];
			}

			for (int r = start.row + 1; r <= end.row; r++) {
				for (int c = start.col + 1; c <= end.col; c++) {
					if (!obs[r][c]) {
						dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
					}
				}
			}
		}

		System.out.println(dp[N][M]);
	}
}

---

테스트 케이스

// case 1:
5 8 4 4
1 2
2 5
3 5
4 7
1 5
2 2
2 7
3 6
ans: 4

// case 2:
5 8 4 4
1 2
2 5
3 3
4 7
1 5
2 2
2 7
3 6
ans: 0

// case 3:
5 8 4 0
1 2
2 5
3 3
4 7
ans: 0

// case 4:
1 1 1 0
1 1
ans: 1