백준 1103 게임

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

1103번: 게임

보드에 적힌 수만큼 상하좌우로 이동할 수 있을 때 보드를 벗어나거나 구멍에 빠질 때까지 움직일 수 있는 횟수를 구하는 문제입니다. 루프가 발생하면 -1을 출력합니다.

 

처음에 dfs만으로 풀려다 계속 시간초과가 나서 dp를 추가하여 풀었습니다. 

dfs로 돌면서 밖에 가거나 구멍인 경우, 해당 위치에서 더 이상 움직일 수 없으므로 0을 리턴하고,

이동 가능한 경우, 상하좌우로 움직이면서 dfs를 돈 결과에 +1을 하면 됩니다. (+1 : 현재 위치에서 상하좌우로 가는 거 카운트) 그 결과와 현재 위치의 dp 값을 비교하여 최대값이 현재 위치에서 계산된 최대 결과입니다.

 

그리고 dp를 이용해 이미 해당 지점의 최대 결과를 알고 있다면 더 이상 진행할 필요가 없으므로 dp값을 리턴합니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int map[51][51];
// H 대신 0으로 처리
int n, m;
bool inf;

// 상하좌우
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, 1, -1};

int dp[51][51]; // dp로 y,x 위치까지 탐색했을 때 최대값 계산
bool visited[51][51]; // 방문 여부 확인 (루프 체크 )

void init()
{
    cin >> n >> m;
    
    string s;
    for(int i = 0; i < n; i++) {
        cin >> s;
        for(int j = 0; j < s.size(); j++) {
            if(s[j] == 'H') {
                map[i][j] = 0;
            }
            else {
                map[i][j] = s[j] - '0';
            }
            dp[i][j] = -1;
            visited[i][j] = false;
        }
    }
    
    inf = false; // 무한루프 체크용 
}

// dfs 돌면서 지나온 애들 다 저장
// 만약 돈 지점 도착 시 무한루프 발생
// 그거 아니면 정답 후보

int dfs(pair<int, int> p)
{
    // p : 현재 위치, cnt : 현재까지 카운트된 횟수, vec : 지나온 위치 
    
    // 밖인 경우 
    if(p.first < 0 || p.first >= n || p.second < 0 || p.second >= m) {
        return 0;
    }
    
    // 구명인 경우 
    int x = map[p.first][p.second];
    if(x == 0) {
        return 0;
    }
    
    // 현재 지나온 길에 있는 경우
    if(visited[p.first][p.second]) {
        inf = true;
        return 0;
    }
    
    // 이미 계산된 경우 
    if(dp[p.first][p.second] != -1)
        return dp[p.first][p.second];
    
    visited[p.first][p.second] = true;
    
    // 이동 가능한 경우
    for(int i = 0; i < 4; i++) {
        int ny = p.first + dy[i] * x;
        int nx = p.second + dx[i] * x;
        
        pair<int,int> np = {ny, nx};
        
        dp[p.first][p.second] = max(dp[p.first][p.second], dfs(np) + 1);
    }
    
    visited[p.first][p.second] = false; // 다음 방향 돌려고 초기화 
    
    return dp[p.first][p.second];
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    pair<int,int> start = {0, 0};
    int result = dfs(start);
    
    if(inf) {
        cout << -1;
    }
    else {
        cout << result;
    }
    
}