백준 - 2411 아이템 먹기

[Gold IV] 아이템 먹기 - 2411

문제 링크

성능 요약

메모리: 2080 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 4월 4일 23:11:05

문제 설명

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

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

입력

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

출력

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

풀이과정

가능한 경로 수를 모두 찾는 문제로 전형적인 dp문제이다.
꼭 방문해야만 하는 위치들 사이의 경로 수를 더하여 구할 수 있다.

아이템 위치 입력받기

아이템 위치는 꼭 방문해야만 하는 위치들이다. 벡터에 저장한다.
1,1 부터 N,M 을 포함하는 인덱스의 맵이 입력되는데, 0,0부터로 바꿔주기 위해서 N,M과 입력되는 위치를 모두 1씩 줄여주었다.

꼭 방문해야만 하는 위치 정렬

아이템 뿐만이 아니라 시작위치, 종료위치 또한 꼭 방문해야하므로 벡터에 넣는다. 입력되는 아이템 위치의 순서가 보장되어 있지 않으므로 오름차순으로 정렬한다.

장애물 위치 입력받기

장애물 위치를 입력받아 해당 위치를 bool 배열에 1로 저장했다. 역시 인덱스를 1씩 줄여주었다.

시작점 경우의 수 초기화

시작점의 경우의 수는 무조건 1이다. 만약 시작점에 장애물이 있더라도, bool 배열을 확인하여 경우의 수를 세지 않을 수 있으므로 무조건 1로 표시한다.

경우의 수 세기

꼭 거쳐가야하는 위치 사이의 경우의 수를 계산한다.
벡터의 1번 부터 시작한다.

2중 반복문으로 탐색하여 경우의 수를 센다.
v[i-1]의 x좌표 ~ v[i]의 x좌표
v[i-1]의 y좌표 ~ v[i]의 y좌표

이 때 v[i-1]의 x,y 위치에서는 경우의 수를 계산하지 않는다.
만약 이전 위치가 0,0이라면, 0,0은 계산하지 않고 넘어간다.

경우의 수 계산 방법

현재 위치로 올 수 있는 경우는 두 가지가 있다.

1. 왼쪽에서 오는 경우 (i, j-1)
2. 밑에서 오는 경우 (i-1, j)
   (지도의 왼쪽 아래가 0,0이므로 밑에서 오는 경우는 i-1,j가 된다.)
   이 때 bool 배열을 확인하여 이전 위치에 장애물이 없다면 현재 위치의 경우의 수에 더해준다.

정답 출력

0,0부터 아이템을 거쳐서 경우의 수를 세주었고, 정답은 N,M 위치의 경우의 수가 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define X first
#define Y second
#define MX 105
using namespace std;
int N, M, A, B, x, y, map[MX][MX];
bool p[MX][MX];
vector<pair<int, int>> v;

void solve(int a, int b, int c, int d) {
    for (int i = a; i <= c; i++) {
        for (int j = b; j <= d; j++) {
            if (p[i][j] || i == a && j == b) continue;
            if (!p[i - 1][j]) map[i][j] += map[i - 1][j];
            if (!p[i][j - 1]) map[i][j] += map[i][j - 1];
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> A >> B;
    while (A--) {
        cin >> x >> y;
        v.push_back({ x - 1,y - 1 });
    }

    N--; M--;
    v.push_back({ 0,0 }); v.push_back({ N, M });
    sort(v.begin(), v.end());

    while (B--) {
        cin >> x >> y;
        p[x - 1][y - 1] = 1;
    }

    map[0][0] = 1;
    for (int i = 1; i < v.size(); i++) 
        solve(v[i - 1].X, v[i - 1].Y, v[i].X, v[i].Y);

    cout << map[N][M];
}