[백준] 1103 - 게임

https://www.acmicpc.net/problem/17070

이 문제와 상당히 유사하고, 

2019/10/13 - [Algorithms/DP] - [백준] 17070 - 파이프 옮기기에 위 문제의 풀이를 포스팅 하였으니 왜 같다고 생각한지 확인 해보시길...

먼저 이 문제는 dfs로 풀면 아주, 상당히, 시간이 걸릴 문제다.

그렇기 때문에, dfs에 dp를 먹여서 가지도 쳐 주고, 무한 루프도 쉽게 찾을 수 있다.

한번 끝까지 간(범위를 벋어나거나, 구멍에 빠지거나) 한 동전은 돌아오며 그 길이를 저장한다.

즉, 좌표에 끝까지 갔을 경우, 최대 몇번까지 움직일 수 있는지를 저장한다.

한마디로 구멍이나, 범위를 벋어난 동전은 재귀 호출에 return 할때 1, 2, 3....순으로 돌아오는 좌표에 저장이 될 것이다.

만약 다른 경로로 탐색하다 이미 지났던 점을 만날 경우, 지났던 점의 좌표에 해당하는 dp값을 return 받으며 1씩 증가시키며 return한다.

즉, 그 경로로 가다보면, 어짜피 지나왔던 점에 횟수만큼 더 움직일 것이니, 더 탐색할 것 없이 return을 받으면 된다~~ 라는 논리가 된다.

그럼 무한루프는 어떻게 check를 해 주느냐? 단순하다

그냥 visit배열 하나로 방문점만 제 때 체크해주면 된다. 

여기서 혼동할 점은, dp에서 이미 방문했던 점은 왜 안되느냐? 라는 것인데, 그건 다른 중간이 다른 경로고, 결과는 같다 라는 점이다.

집에서 세탁소에 들렀다 편의점을 간다고 가정할 때, 왼쪽골목으로 돌아서 세탁소를 거쳐 편의점을 가느냐, 오른쪽 골목으로 돌아서 세탁소를 거쳐 편의점을 가느냐 그 차이일 뿐...!

무한 loop는 지금 가는 경로에서 방문한 점을 만났을 경우만 성립함으로 그 경우만 check해주면 된다.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <memory.h>
#define SIZE 52
#define MAX(X, Y) (X) > (Y) ? (X) : (Y)
using namespace std;
 
int map[SIZE][SIZE], dp[SIZE][SIZE], visit[SIZE][SIZE];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, M;
 
int dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= M || y >= N || !map[y][x]) return 0;
    if (visit[y][x]) { cout << -1 << endl; exit(0); }
    if (dp[y][x]) return dp[y][x];
    visit[y][x] = 1;
    for (int i = 0; i < 4; i++)
        dp[y][x] = MAX(dp[y][x], dfs(x + map[y][x] * dx[i], y + map[y][x] * dy[i]) + 1);
    visit[y][x] = 0;
    return dp[y][x];
}
 
int main(void) {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            char c;
            cin >> c;
            if (c <= '9') map[i][j] = c - '0';
        }
 
    cout << dfs(0, 0) << endl;
 
    return 0;
}