백준, boj) 1103. 게임 ( C/ C++)

1. 문제 링크

www.acmicpc.net/problem/1103

1103번: 게임

2. 문제 개요

동전을 움직일 건데,

  i) 동전이 있는 곳에 쓰여 있는 숫자 X를 본다.

  ii) 위, 아래, 왼쪽, 오른쪽 방향 중에 한 가지를 고른다

  iii) 동전을 위에서 고른 방향으로 X만큼 움직인다, 이때, 중간에 있는 구멍은 무시한다.

 

3. 문제 힌트

정답률이 상당히 낮다.  나도 문제 풀 때 고려하는 거 다 고려했다고 생각했는데 틀려버린..

 

고려해야 하는 것부터 적어본다면,

일단, 보기의 정답이 5인 것도 이해가 안 됐다.

 

'보드의 바깥으로 나가는 것' or '구멍에 빠지는 것' 도 움직이는 것이기 때문에 1회로 쳐주어야 한다.!!

 

무한으로 움직일 수 있는 것. 이거는 2칸 움직일 수 있는 칸에서 또 2칸 움직일 수 있는 칸으로 가는 경우만 생각했는데,,

3	..	..	2
..	..	..
2	..	..	3

위의 표처럼 되어있다면 loop가 생길 것이고 이거 또한 무한으로 놓을 수 있다는 점을 잊지 말고 풀이하자.. (이거 때문에 맞왜틀 50분..)

 

그리고 이런 문제 특성상 DP 카테고리에서 들어왔다면 이해를 바로 했겠지만, DFS카테고리에서 들어왔다면 DP가 필수이다. 왜냐하면 이전에 또 갔던 곳을 가면 시간 복잡도가 지수로 넘어가버리기 때문이다. 그래서 dp를 '해당 칸에 도착했을 경우 최대 갈 수 있는 거리'로 정의하고 방문한 적이 있다면 그 값을 바로 사용해주자. 여기서 방문은 loop를 찾는 방문과는 조금 다름.

 

 

4. 문제 풀이

문제 자체는 정말 간단히 DP만 안다면 풀이할 수 있다. 워낙 고려해야 하는 점이 많아서 그렇지...

 

그냥 4방향 모두 탐색하고 범위 안이라면 다시 dfs를 실행해주고, 그렇지 않다면 0을 반환해주자. 

 

그럼 저 loop를 어떻게 처리해주는지 알아보자.

visited변수를 주어 하나의 줄기(DFS)로 탐색을 할 때 visited 체크를 한다. 그 말은 결국 DFS에서 Depth가 내려갈 때는 (반환해서 다시 올라갈 때) visited을 false로 바꿔줘야 함을 의미한다. 그렇지 않으면 loop가 아닌데 그냥 방문했다는 이유로 함수가 끝나버릴 수 있기 때문이다. 

 

최댓값을 구했냐 자체는 메모이제이션으로 즉시 반환을 해서 구하고 있기 때문에 visited변수는 그냥 단순히 loop을 이루는지 안 이루는지 체크만 하면 된다.

 

이해가 한 번에 팟! 하고 안 될 거 같은데, 코드를 보면 아마 이해가 될 거라고 생각합니다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;

char map[50][50];
int dp[50][50];
bool visited[50][50];
int n, m;

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

int dfs(int cy, int cx)
{
	//boundary check
	if (cy < 0 || cx < 0 || cx >= m || cy >= n || map[cy][cx] == 'H')
		return 0;

	if (visited[cy][cx])
	{
		printf("-1");
		exit(0);
	}

	int &cache = dp[cy][cx];
	if (cache != -1)
		return cache;

	visited[cy][cx] = true;

	cache = 0;
	for (int dir = 0; dir < 4; ++dir) {

		int ny = cy + dy[dir] * (map[cy][cx] - '0');
		int nx = cx + dx[dir] * (map[cy][cx] - '0');

		cache = max(cache, dfs(ny, nx) + 1);
	}

	visited[cy][cx] = false;
	return cache;
}

int main()
{
	scanf("%d %d", &n, &m);

	memset(dp, -1, sizeof(dp));

	for (int i = 0; i < n; ++i)
		scanf("%s", &map[i]);

	printf("%d",dfs(0, 0));

	return 0;
}

 

 

6. 실행 결과