[백준] 10164 격자상의 경로

문제

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.) 

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

 

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라. 

입력

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다. 

 

그래프에서의DP문제입니다.

한 지점에서 오른쪽, 아래방향으로만 움직일 수 있을때, 한지점에서 목적지까지 이동할 수 있는 경우의 수는 

그 지점을 기준으로 아래,오른쪽 지점에서 목적지까지 움직이는 경우의 수의 합과 같습니다.

재귀로 작성합니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { 0,1 }, dx[] = { 1,0}, INF = 987654321;

using namespace std;

int mp[16][16], dp[16][16], N, M, K;
pi c;
int dfs(pi c, pi t) {
	if (c.first == t.first && c.second == t.second)return dp[c.first][c.second]=1;
	if (dp[c.first][c.second] != -1)return dp[c.first][c.second];
	dp[c.first][c.second] = 0;
	rep(i, 2) {
		int ny = c.first + dy[i];
		int nx = c.second + dx[i];
		if(ny>=1 && ny<=t.first && nx>=1 && nx<=t.second)
			dp[c.first][c.second] += dfs({ ny,nx }, t);
	}
	return dp[c.first][c.second];
}
int main() {
	FAST;
	cin >> N >> M >> K;
	int cnt = 0;
	memset(dp, -1, sizeof(dp));
	REP(i, N) {
		REP(j, M) {
			if ((++cnt) == K)c = { i,j };
		}
	}
	if (K == 0) {
		cout << dfs({1,1},{N,M});
	}
	else {
		int A = dfs({ 1,1 }, c);
		dp[c.first][c.second] = -1;
		int B = dfs(c, { N,M });
		cout << A * B;
	}
}