[백준] 1103번 게임

1103번: 게임

처음에 재귀로 그냥 DFS를 구현하니까 시간 초과 걸렸었다.

중복되는 연산이 있기 때문에 DP로 최댓값을 저장해주면서 돌려야 했다.

 

DP [i][j] =  i, j에서 상 하 좌 우로 갈 때 얻는 최댓값

이라 지정하고

 

범위를 벗어나거나 구멍을 만나는 경우는 게임 종료

-> 어딜 더 움직일 수 없으므로 0 반환

 

방문했던 곳을 다시 방문하는 경우는 사이클이 생겨 무한 번 움직일 수 있는 경우이므로

-> -1을 출력하고 아예 종료

 

DP에 값이 있는 경우

-> 이미 최댓값이 저장되어 있는 상태이므로 DP 값 반환

 

그 외의 경우

-> 현재 위치를 방문한 상태로 체크해준 후

상 하 좌 우로 재귀를 통해 움직이고

(한 번 움직일 때마다 + 1을 해준다)

이때 재귀에서 돌아올 때 반환되는 값들 중 가장 큰 값을 DP에 저장한다.

다 움직였으면 현재 위치의 방문 값을 false로 다시 바꿔준다.

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int N, M, Max;
int board[51][51], dp[51][51], dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
bool visited[51][51] = { false };
int Dfs(int X, int Y) {
	if (X < 0 || X >= N || Y < 0 || Y >= M) return 0; //보드 바깥으로 나간 경우
	else if (board[X][Y] == -1) return 0; //구멍에 빠진 경우
	else if (visited[X][Y]) { //무한번 움직일 수 있는 경우
		cout << "-1";
		exit(0);
	}
	else if (dp[X][Y] != -1) return dp[X][Y];
	visited[X][Y] = true;
	for (int i = 0; i < 4; i++) {
		int x = X + dx[i] * board[X][Y], y = Y + dy[i] * board[X][Y];
		dp[X][Y] = max(dp[X][Y], Dfs(x, y) + 1); //X,Y에서 x,y로 갈 때 얻는 최댓값 저장
	}
	visited[X][Y] = false;
	return dp[X][Y];
}

int main() {
	string a;
	cin >> N >> M;
	for (int n = 0; n < N; n++) {
		cin >> a;
		for (int m = 0; m < M; m++) {
			if (a[m] == 'H') board[n][m] = -1;
			else board[n][m] = a[m] - '0';
		}
	}
	memset(dp, -1, sizeof(dp));
	cout << Dfs(0,0);
	return 0;
}