BOJ 1513 - 경로 찾기

문제

N x M 크기인 지도에 1부터 C까지 번호가 매겨진 오락실 C개가 존재한다.
직전에 방문한 오락실의 번호가 이번에 방문할 오락실의 번호보다 작은 경우 방문할 수 있다.
이때 (1, 1)에서 출발하여 (N, M)으로 가는 경로들 중 오락실을 [1, C]개 지나는 경로의 개수를 각각 출력하면 된다.

풀이

dp를 아래와 같이 설계한다.
dp(i)(j)(c)(p) = (i, j)의 좌표에 위치하고 현재까지 방문한 오락실의 개수가 c개이며 가장 최근에 방문한 오락실의 번호가 p인 경로의 개수

이때 아래와 같이 점화식을 구할 수 있다.

• (i, j)가 오락실일 경우
  dp(i)(j)(c)(p)=dp(i-1)(j)(c-1)([0, p-1]) + dp(i)(j-1)(c-1)([0, p-1])
  • 현재 위치가 오락실이기 때문에 방문한 오락실 수 c는 1이 증가하고 가장 최근의 오락실의 위치는 p로 초기화됨
• (i, j)가 오락실이 아닐 경우
  dp(i)(j)(c)(p)=dp(i-1)(j)(c)(p)+dp(i)(j-1)(c)(p)
  • 가능한 경로만 계산해주면 됨

(1, 1)도 오락실이 될 수 있기 때문에 (1, 1)이 k번째 오락실일 경우 dp(1)(1)(1)(k)=1로 초기화하고,
오락실이 아닐 경우 dp(1)(1)(0)(0)=1로 초기화한다.

소스코드

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#define MOD 1000007
using namespace std;
using pii=pair<int, int>;
using vi=vector<int>;
using vl=vector<long long>;
using lld=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, c;
    cin>>n>>m>>c;
    vector<vi> ar(n, vi(m, 0));
    vector<vector<vector<vl> > > dp(n, vector<vector<vl> >(m, vector<vl>(c+1, vl(c+1, 0))));
    for(int i=0;i<c;i++){
        int r, cc;
        cin>>r>>cc;
        ar[r-1][cc-1]=i+1;
    }
    if(ar[0][0]) dp[0][0][1][ar[0][0]]=1;
	else dp[0][0][0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(ar[i][j]){
                int curc=ar[i][j];
                if(i>0){
                    for(int k=0;k<curc;k++){
                        for(int l=0;l<curc;l++){
                            dp[i][j][k+1][curc]+=dp[i-1][j][k][l];
                            dp[i][j][k+1][curc]%=MOD;
                        }
                    }
                }
                if(j>0){
                    for(int k=0;k<curc;k++){
                        for(int l=0;l<curc;l++){
                            dp[i][j][k+1][curc]+=dp[i][j-1][k][l];
                            dp[i][j][k+1][curc]%=MOD;
                        }
                    }
                }
            }
            else{
                if(i>0){
                    for(int k=0;k<=c;k++){
                        for(int l=0;l<=c;l++){
                            dp[i][j][k][l]+=dp[i-1][j][k][l];
                            dp[i][j][k][l]%=MOD;
                        }
                    }
                }
                if(j>0){
                    for(int k=0;k<=c;k++){
                        for(int l=0;l<=c;l++){
                            dp[i][j][k][l]+=dp[i][j-1][k][l];
                            dp[i][j][k][l]%=MOD;
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<=c;i++){
        int ans=0;
        for(int j=0;j<=c;j++){
            ans+=dp[n-1][m-1][i][j];
            ans%=MOD;
        }
        cout<<ans<<' ';
    }
    return 0;
}

• 좌표는 편의상 [0, n-1], [0, m-1]을 사용하였다.

풀고나서

• 상태공간이 4개가 넘어가면 데이터의 크기도 작아지는데, 이것을 이용해서 풀이 방법이 dp라고 유추할 수도 있을 것 같다.