[BOJ] 2411번 아이템 먹기

문제

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

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

입력

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

출력

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

예제

// 입력
5 8 4 4
1 2
2 5
3 5
4 7
1 5
2 2
2 7
3 6

// 출력
4

코드

// cpp 17
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

constexpr int OBSTACLE = -1;

struct Pos
{
	int R;
	int C;

	// sort를 위한 연산자 오버로딩
	constexpr bool operator<(const Pos& other) { return R < other.R; }
};

int N, M, A, B;
int map[101][101];

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

	// 이 문제는 DP로 (cur, next)의 경로 수를 구해서 모두 곱해주면 된다.

	// 다음 위치를 담기 위한 변수
	vector<Pos> nexts;
	nexts.reserve(200 * sizeof(Pos));

	// 맵을 상하대칭시켜 표현할 수 있다.
	// 그러므로 2차원 배열을 이용할 수 있다.
	cin >> N >> M >> A >> B;
	for (int i = 0; i < A; i++)
	{
		int r, c;
		cin >> r >> c;
		nexts.push_back({ r, c });
	}
	for (int i = 0; i < B; i++)
	{
		int r, c;
		cin >> r >> c;
		map[r][c] = OBSTACLE;
	}
	nexts.push_back({ N, M });
	sort(nexts.begin(), nexts.end());

	// 경로 수를 메모이제이션 할 배열을 따로 두어도 되지만,
	// map 위에 나타낼 수 있으므로 직접 나타내겠다.
	Pos cur = { 1, 1 };
	map[cur.R][cur.C] = 1;
	for (const auto& next : nexts)
	{
		int prev = map[cur.R][cur.C];

		for (int r = cur.R; r <= next.R; r++)
		{
			if (map[r][cur.C] == OBSTACLE)
				break;
			map[r][cur.C] = prev;
		}
		for (int c = cur.C; c <= next.C; c++)
		{
			if (map[cur.R][c] == OBSTACLE)
				break;
			map[cur.R][c] = prev;
		}
		for (int r = cur.R + 1; r <= next.R; r++)
		{
			for (int c = cur.C + 1; c <= next.C; c++)
			{
				if (map[r][c] != OBSTACLE)
				{
					int bottom = (map[r - 1][c] < 0) ? 0 : map[r - 1][c];
					int left = (map[r][c - 1] < 0) ? 0 : map[r][c - 1];
					map[r][c] = bottom + left;
				}
			}
		}

		cur = next;
	}
	cout << map[N][M];
}