[백준] 1103번 게임 C++ 코드

코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m,dp[53][53],visited[53][53];
string s;
char a[53][53];
// H는 구멍, 구멍이나 밖으로 나가면 게임 끝
// 왼쪽 위는 숫자
// 무한번 움직일 수 있는 경우는 -1 출력 -> 어떻게 찾지

int go(int x, int y) {
    if(x >= n || y >= m || x < 0 || y < 0) return 0; // 바깥쪽으로 간 경우
    if(a[x][y] == 'H') return 0; // 구멍에 도착한 경우
    if(dp[x][y] != -1) return dp[x][y]; // 메모이제이션
    
    if(visited[x][y] == 1) {
        cout << -1 << '\n'; // 방문했는데 다시 방문한 경우 -> 사이클 생성
        exit(0);
    }
    int move = a[x][y] - '0';
    visited[x][y] = 1; // 방문처리
    int u = go(x - move, y) + 1;
    int d = go(x + move, y) + 1;
    int l = go(x, y - move) + 1;
    int r = go(x, y + move) + 1;
    visited[x][y] = 0; // 원상복구
    dp[x][y] = max({u,d,l,r});
    return dp[x][y];
}

int main() {
    cin >> n >> m;
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < n; i++) {
        cin >> s;
        for(int j = 0; j < m; j++) {
            a[i][j] = s[j];
        }
    }
    cout << go(0,0) << '\n';
    return 0;
}

풀이

완전탐색을 해야할 거 같은데, 이전의 상태를 이용할 수 있을 거라 생각해 dp를 이용했다. dp를 사용할 때 고려해야할 조건은 유향 비순환 그래프 여부이다. 이 문제에서는 사이클이 생기는 순간 -1을 출력하며 종료한다는 조건이 있기 때문에 유향 비순환이라 가정하고 문제에 접근했다. 이미 방문한 곳인지 확인하기 위해 방문 배열을 이용했고 탐색이 끝나면 원상복구하는 작업을 통해 다음 탐색에 영향을 주지 않도록 했다.

이미 방문한 곳을 방문했다면 -1을 출력하고 프로그램을 종료한다. 그렇지 않다면 최대 움직일 수 있는 횟수를 구한다.