Cow Hopscotch

알고리즘 구분 : 다이나믹 프로그래밍

문제

Just like humans enjoy playing the game of Hopscotch, Farmer John's cows have invented a variant of the game for themselves to play. Being played by clumsy animals weighing nearly a ton, Cow Hopscotch almost always ends in disaster, but this has surprisingly not deterred the cows from attempting to play nearly every afternoon.

The game is played on an R by C grid (2 <= R <= 100, 2 <= C <= 100), where each square is labeled with an integer in the range 1..K (1 <= K <= R*C). Cows start in the top-left square and move to the bottom-right square by a sequence of jumps, where a jump is valid if and only if

1) You are jumping to a square labeled with a different integer than your current square,

2) The square that you are jumping to is at least one row below the current square that you are on, and

3) The square that you are jumping to is at least one column to the right of the current square that you are on.

Please help the cows compute the number of different possible sequences of valid jumps that will take them from the top-left square to the bottom-right square.

입력
The first line contains the integers R, C, and K. The next R lines will each contain C integers, each in the range 1..K.

출력
Output the number of different ways one can jump from the top-left square to the bottom-right square, mod 1000000007.

예제 입력 1
4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1
예제 출력 1
5

문제 풀이

위의 문제는 10752. Cow Hopscotch와 동일한 유형으로 일부만 조금 바뀐 문제다. 그렇기에, 위의 문제를 풀 때와 동일하게 DFS로 접근하였으나, 탐색해야 하는 범위가 넓어짐으로 인해 시간초과를 받았다.

시간 초과 소스 코드

#include <bits/stdc++.h>

using namespace std;

int r, c, k;
long long result;
vector<vector<int>> graph;
void dfs(int x, int y);

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

	cin >> r >> c >> k;
	for(int i = 0; i < r; i++) {
		vector<int> temp;
		for(int j = 0; j < c; j++) {
			int input;
			cin >> input;
			temp.push_back(input);
		}
		graph.push_back(temp);
	}
	
	result = 0;
	dfs(0, 0);
	
	cout << result % 1000000007 << endl;
	
	return 0;
}

void dfs(int x, int y) {
	if(x == r - 1 && y == c - 1) {
		++result;
		return ;
	}
	
	for(int i = x + 1; i < r; i++) {
		for(int j = y + 1; j < c; j++) {
			if(graph[x][y] != graph[i][j]) {
				dfs(i, j);
			}
		}
	}
}

// tle

그렇기에, 시간복잡도를 줄이기 위하여, Queue를 이용해 탐색 횟수를 최소화하고자 하였는데, 탐색 범위가 커지고, input값이 다양할 경우, 메모리 초과를 받는 다는 것을 알게 되었다.

메모리 초과 소스 코드

#include <bits/stdc++.h>

using namespace std;

int r, c, k;
vector<vector<int>> graph;
int dp[101][101];
void solve(int x, int y);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> r >> c >> k;
	for(int i = 0; i < r; i++) {
		vector<int> temp(c);
		for(int j = 0; j < c; j++) {
			cin >> temp[j];
		}
		graph.push_back(temp);
	}
	
	memset(dp, 0, sizeof(dp));
	solve(0, 0);
	
	return 0;
}

void solve(int x, int y) {
	pair<int, int> now;
	queue<pair<int, int>> q;
	
	q.push({x, y});
	dp[x][y] = 1;
	while(!q.empty()) {
		now = q.front();
		q.pop();
		
		for(int i = now.first + 1; i < r; i++) {
			for(int j = now.second + 1; j < c; j++) {
				if(graph[now.first][now.second] != graph[i][j]) {
					dp[i][j] += 1;
					q.push({i, j});
				}
			}
		}
	}
	
	/*
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	*/
	
	cout << dp[r - 1][c - 1] << endl;
}  

문제를 너무 어렵게 바라보고 있는 것 같아, 쉽게 생각해보았더니, 완전 탐색하면서, dp값이 1 이상인, 즉, 연결 방법이 있는 경우에 한해 해당 위치에서 다음 연결고리를 찾을 수 있도록 하는 방식으로 구현해보고자 하였더니 정답 판정을 받았다. 시간복잡도는 반복문이 총 4번 중첩되어 사용되기에, O(R^2*C^2)가 된다. 그러나 R, C가 최대 100이며, 아래의 소스 코드를 보면 move메소드는 사실상 O(RC)보다 작은 시간복잡도를 가지게 되기에, 충분히 문제의 시간 제한 안에 풀 수 있다.

• 여기서 조심해야할 부분은 정답을 구하는 과정에서 나는 마지막 모든 계산이 진행된 이후에, mod 1000000007을 진행했으나, "틀렸습니다."라는 판정을 받았다. 혹시 몰라, dp 계산 과정에서 나눗셈을 진행할 수 있도록 하였더니 정답 판정을 받았다. 문제에서는 총 결과 값에서 나누라고 이해를 했는데, 영어 실력이 부족했던 것 같다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

int r, c, k;
long long dp[101][101];
vector<vector<int>> graph;
void move(int nx, int ny);
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> r >> c >> k;
	for(int i = 0; i < r; i++) {
		vector<int> temp(c);
		for(int j = 0; j < c; j++) {
			cin >> temp[j];
		}
		graph.push_back(temp);
	}
	
	memset(dp, 0, sizeof(dp));
	solve();
	
	return 0;
}

void move(int nx, int ny) {
	for(int i = nx + 1; i < r; i++) {
		for(int j = ny + 1; j < c; j++) {
			if(graph[nx][ny] != graph[i][j]) {
				dp[i][j] += dp[nx][ny];
				dp[i][j] %= 1000000007;
			}
		}
	}
}

void solve() {
	dp[0][0] = 1;	

	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			if(dp[i][j] > 0) {
				move(i, j);
			}
		}
	}
	
	
	
	cout << dp[r - 1][c - 1] << endl;
}

• 문제 출처 : https://www.acmicpc.net/problem/10748
• 해당 풀이는 백준에서 "맞았습니다" 판정을 받았습니다.