[백준] 2411번: 아이템 먹기

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

2411번: 아이템 먹기

---

특정한 위치를 지날 때의 경로 개수를 구하는 dp 문제다.

 

1. 문제 조건

1) (1, 1) → (N, M) 까지 도달하는 경로의 수를 출력해야 한다.

2) 위쪽과 오른쪽으로만 이동할 수 있다.

3) 이동 중에 모든 아이템을 먹어야 한다.

4) 장애물은 지날 수 없다.

 

2. dp 배열 정의

전형적인 경로 탐색 문제다.

다만 모든 아이템을 먹어야 한다는 점에서, 아이템을 기준으로 한 경로 찾기 문제가 된다.

우선 일반 경로 개수 구하는 문제처럼, dp 배열을 2차원으로 정의한다.

#define MAXN 101
#define MAXM 101

// dp[y][x] = (y, x) 까지 도달하는 경로의 개수
int dp[MAXN][MAXM];

문제에서 장애물의 위치와 아이템의 위치가 주어진다.

장애물의 위치는 bool 타입으로 지나갈 수 있는지 기록하고

아이템의 위치는 pair 타입으로 좌표 자체를 저장한다.

#define Y first		// 아이템 y 좌표
#define X second	// 아이템 x 좌표

typedef pair<int, int> pii;

// isBlocked[y][x] = (y, x)가 장애물이면 true
bool isBlocked[MAXN][MAXM];

pii item[MAXN * MAXM];	// 최종적으로 아이템을 정렬된 순서로 저장
pii temp[MAXN * MAXM];	// merge sort를 위한 임시 아이템 배열

 

3. 해결법

우선 특정한 위치를 지나는 경로의 개수 문제는

(그 지점까지의 경로의 수) × (그 지점부터 목적지까지의 경로의 수) 로 계산할 수 있다.

 

따라서 모든 아이템을 먹으려면,

이전 아이템의 위치부터 다음 아이템의 위치까지의 경로 개수를 각각 구해서 모두 곱하면 된다.

물론 처음에는 시작점인 (1, 1)부터, 마지막에는 목적지인 (N, M)까지 구해야 한다.

 

한편, 이동은 위쪽과 오른쪽으로밖에 하지 못한다.

따라서 모든 아이템을 먹으려면, 입력받은 아이템의 좌표를 정렬시켜야 한다.

 

정렬을 위해 merge sort를 구현해서 사용했는데,

y 좌표가 더 작은 것이, 만약 같다면 x 좌표가 더 작은 것이 앞에 오도록 정렬한다.

정렬 후에는, 구현의 편의상 맨 마지막에 목적지인 (N, M)을 추가해주면 좋다.

mergeSort(0, A-1);		// 아이템은 0 ~ (A-1) 까지 들어가 있다.
item[A] = pii(N, M);	// A번에 목적지를 추가한다.

item에 대해 for문을 돌며, 시작 좌표와 도착 좌표를 갱신해준다.

중간에 장애물이 있으면 더이상 볼 필요가 없다는 점을 잊지 말자.

그러면서 여느 경로 dp 문제와 같이 도착 좌표에서의 dp 값을 누적해서 곱해주면 답이 된다.

---

전체 풀이 코드는 다음과 같다.

#include <iostream>
using namespace std;

#define MAXN 101
#define MAXM 101

#define Y first
#define X second

typedef pair<int, int> pii;

bool isBlocked[MAXN][MAXM];
pii item[MAXN*MAXM];
pii temp[MAXN*MAXM];

int dp[MAXN][MAXM];

bool compare(pii a, pii b) {
	int cmp = b.Y - a.Y;
	if(cmp == 0) cmp = b.X - a.X;

	return cmp > 0;
}

void mergeSort(int start, int end) {
	if(start >= end) return;

	int mid = (start + end) >> 1;
	mergeSort(start, mid);
	mergeSort(mid+1, end);

	int left = start;
	int right = mid + 1;
	int idx = start;
	
	while(left <= mid && right <= end) {
		temp[idx++] = compare(item[left], item[right]) ?
					  item[left++] : item[right++];
	}

	while(left <= mid) temp[idx++] = item[left++];
	while(right <= end) temp[idx++] = item[right++];

	for(int i=start; i<=end; i++) item[i] = temp[i];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, A, B; cin >> N >> M >> A >> B;
	for(int a=0; a<A; a++) {
		int y, x; cin >> y >> x;
		item[a] = pii(y, x);
	}

	mergeSort(0, A-1);
	item[A] = pii(N, M);

	for(int b=0; b<B; b++) {
		int y, x; cin >> y >> x;
		isBlocked[y][x] = true;
	}

	int startY = 1, startX = 1;
	int endY, endX;
	int ans = 1;
	for(int i=0; i<=A; i++) {
		endY = item[i].Y, endX = item[i].X;

		dp[startY][startX] = 1;
		for(int y=startY; y<=endY; y++) {
			if(isBlocked[y][startX]) break;
			dp[y][startX] = 1;
		}

		for(int x=startX; x<=endX; x++) {
			if(isBlocked[startY][x]) break;
			dp[startY][x] = 1;
		}

		for(int y=startY+1; y<=endY; y++) {
			for(int x=startX+1; x<=endX; x++) {
				if(isBlocked[y][x]) continue;

				dp[y][x] = dp[y-1][x] + dp[y][x-1];
			}
		}

		ans *= dp[endY][endX];
		startY = endY, startX = endX;
	}

	cout << ans << '\n';

	return 0;
}