BOJ 1103번 게임

www.acmicpc.net/problem/1103

1103번: 게임

문제

형택이는 1부터 9까지의 숫자와, 구멍이 있는 직사각형 보드에서 재밌는 게임을 한다.

일단 보드의 가장 왼쪽 위에 동전을 하나 올려놓는다. 그다음에 다음과 같이 동전을 움직인다.

1. 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.
2. 위, 아래, 왼쪽, 오른쪽 방향 중에 한가지를 고른다.
3. 동전을 위에서 고른 방향으로 X만큼 움직인다. 이때, 중간에 있는 구멍은 무시한다.

만약 동전이 구멍에 빠지거나, 보드의 바깥으로 나간다면 게임은 종료된다. 형택이는 이 재밌는 게임을 되도록이면 오래 하고 싶다.

보드의 상태가 주어졌을 때, 형택이가 최대 몇 번 동전을 움직일 수 있는지 구하는 프로그램을 작성하시오.

 

입력

줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 형택이가 동전을 무한번 움직일 수 있다면 -1을 출력한다.

 

-------------------------------------------------------------------------------------------------------

 

오랜만에 백준을 풀면서 포스팅을 했습니다.

 

이번 문제는 난이도 골드1의 게임 문제를 풀어보겠습니다.

 

항상 그렇듯 문제를 풀기 전에 어떤 식으로 풀 것인지 접근하는 것이 중요하다고 생각합니다.

 

문제를 읽어보면 기본적으로 dfs, bfs 같은 탐색을 이용한다는 것을 유추할 수 있고,

N이 50정도면 최대한 이동할 수 있는 범위를 찾고자 할 때 매 구간 캐시값을 저장해두지 않으면 시간초과가 날 것이므로 캐시값을 저장해두는 다이나믹 프로그래밍 방식인 것을 유추할 수 있습니다.

 

dp의 차원을 정할 때는 어떤 정보가 필요할 것인지 고려해줘야 하는데,

현재 문제의 경우에는 단순히 dp[y][x] = 위치 y,x 에서 갈 수 있는 최대한의 이동거리 만을 알면 되기 때문에

3차원, 4차원까지 추가적인 배열을 사용할 필요가 없습니다.

 

이외에는 문제에서 요구하는대로 이동해주면서 가장 많이 이동할 수 있는 거리를 dp를 사용해서

문제를 해결해주시면 됩니다.

 

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
int N, M;
string arr[50];
ll dp[50][50];
int my[4] = { -1,1,0,0 };
int mx[4] = { 0,0,-1,1 };
bool INF = false;

ll dfs(int y, int x) {
	// 이동할 수 없는 경우 이동거리를 -1 만큼 반환해주어서 계산해준다
	if (y < 0 || y >= N || x < 0 || x >= M || arr[y][x] == 'H' || INF) return -1;

	ll& res = dp[y][x];
	// dp[y][x]가 -2 인 경우 이미 한번 방문한 곳이므로
	// 더 확인할 필요없이 무한루프가 된다
	if (res == -2) {
		INF = true;
		return 0;
	}
	// -1이 아닌 경우 dp값을 갖고 있는 것이므로 사용해주면 된다
	if (res != -1) return res;

	// 애초에 방문한 현재 위치를 -2와 같은 임의의 값으로 바꿔주어서
	// 이미 방문한 곳임을 표시해준다
	res = -2;
	ll ans = 0;

	int move = arr[y][x]-'0';

	for (int i = 0; i < 4 && !INF; i++) {
		int yy = y + (my[i]*move);
		int xx = x + (mx[i]*move);
		// 가장 많이 이동할 수 있는 거리를 찾는다
		ans = max(ans, dfs(yy, xx) + 1);
	}

	return res = ans;
}


int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	memset(dp, -1, sizeof(dp));
	dfs(0, 0);
	if (INF) cout << "-1";
	else cout << dp[0][0] + 1;
}