[BOJ 1103] 게임

문제 출처 : https://www.acmicpc.net/problem/1103

 

풀이 :

 

DFS 문제입니다.

BFS로 풀게되면 이전에 온 경로를 알 수 없으므로 DFS를 사용하여 풀어야 합니다.

DFS로 현재까지 온 경로를 체크하면서 오면 중복해서 가는 지점을 찾을 수 있어 무한대로 움직이는 경우를 찾을 수 있습니다.

그리고 시간 단축을 위해 메모이제이션 개념을 사용해 그 지점에 도착했을때 현재 이동한 횟수가 이전에 그 지점에 도달했을때의 횟수보다 작다면 스킵해줍니다.

 

#include<stdio.h>
 
int n, m, ret, visit[50][50], cache[50][50];
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
char arr[51][51];
 
bool dfs(int y, int x, int cnt) {
    if (ret == -1)return true;
    if (cnt > ret)ret = cnt;
    visit[y][x] = 1;
    cache[y][x] = cnt;
    for (int k = 0; k < 4; k++) {
        int ny = y + dy[k] * (arr[y][x] - '0'), nx = x + dx[k] * (arr[y][x] - '0');
        if (ny >= 0 && ny < n&&nx >= 0 && nx < m&&arr[ny][nx] != 'H') {
            if (visit[ny][nx]) {
                ret = -1;
                return true;
            }
            if (cache[ny][nx] && cnt < cache[ny][nx])continue;
            if(dfs(ny, nx, cnt + 1))return true;
        }
    }
    visit[y][x] = 0;
    return false;
}
 
int main() {
    scanf("%d %d\n", &n, &m);
    for (int i = 0; i < n; i++, getchar())for (int j = 0; j < m; j++)scanf("%c", &arr[i][j]);
    dfs(0, 0, 1);
    printf("%d", ret);
}