백준 1103 게임 - C++

자기만 재밌는 게임을 한다고 한다...

 

직사각형 보드에서 동전이 구멍에 빠지거나 보드 바깥으로 

나가지 않는 선에서 게임을 오래 즐기고 싶다고 한다.

 

최대 몇 번 움직이는지는 손으로 구해보면 쉽다.

 

보드의 크기는 최대 50x50이고

각 칸에 적혀있는 숫자는 1~9이며 구멍일 수 있다.

 

몇 가지 점을 빠르게 알 수 있다.

1. 내가 갈 수 있는 칸에 나와 똑같은 숫자가 있으면 무한번 움직일 수 있다.

1-1. 그러므로 무한번이 아닌 경우는 도착하는 숫자가 모두 다르다.

2. 한 번이라도 지나온 칸에 다시 도착한다면 무한번 움직일 수 있다.

2-2. 다시 도착하지 않는다면 반드시 게임은 종료되고, 따라서 그 칸에서

최대한 움직일 수 있는 횟수는 정해져 있다.

 

즉 무한번 움직일 수 있는지 판단은 두 가지로 할 수 있지만, 1번의 경우 

2번에 속해있지만 조금 더 빠른 판단을 할 수 있게 도와주는 것이므로

2번만 구현하되, 속도가 더 필요하면 구현하는 식으로 할 수 있다.

(아래 코드에서는 대충 만들어놓았다.)

 

2-2를 이용하여 각 칸에서 최대한 움직일 수 있는 횟수를 dynamic programming

으로 저장해 놓을 것이고, 기저 케이스는 밖으로 나가거나 구멍에 빠져있는 케이스인 

횟수 0의 경우로 둔다.

횟수 1회로 두지 않는 이유는 케이스 밖으로 나갔을 때 움직일 수 있는 횟수를 0회로 

보기 위해서고, 고로 해당 칸 dp [y][x] = 0 + 1 = 1 이 되도록 만들어주기 위함이다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M;
const int MAXN = 52;
int Map[MAXN][MAXN];
int dp[MAXN][MAXN];
bool isVisited[MAXN][MAXN];

const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,-1,0,1 };

int dfs(int y=1, int x=1) {
	if (y > N || y <= 0 || x > M || x <= 0 || Map[y][x] == 0) {
		return 0;
	}
	else if (isVisited[y][x]) {
		return -1;
	}
	else if (dp[y][x] != -1) {
		return dp[y][x];
	}

	isVisited[y][x] = true;

	for (int i = 0; i < 4; ++i) {
		int ny = y + dy[i] * Map[y][x];
		int nx = x + dx[i] * Map[y][x];
        if (ny<=N && ny>0 && nx<=M && nx>0 && Map[ny][nx] == Map[y][x]) return -1;
		int nextMaxMove = dfs(ny, nx);
		if (nextMaxMove == -1) return -1;
		dp[y][x] = max(dp[y][x], nextMaxMove + 1);
	}

	isVisited[y][x] = false;

	return dp[y][x];
}

int main() {
	scanf("%d %d", &N, &M);

	char input[MAXN];
	for (int i = 1; i <= N; i++)
	{
		scanf("%s", input+1);
		for (int j = 1; j <= M; ++j) {
			if (input[j] == 'H') continue;
			Map[i][j] = input[j] - '0';
		}
	}

	memset(dp, -1, sizeof(dp));
	printf("%d\n", dfs());
	return 0;


}