greentea31's Note

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

풀이 과정

보드에서 해당 칸에 적혀있는 숫자만큼 상하좌우로 이동이 가능할 때, 최대 몇 번 이동이 가능한지 구하는 문제이다.

(A, B)라는 칸에서 상하좌우로 이동해봤더니 4번 이동이 가능했다고 하자. 그러면 (C, D)라는 칸에서 (A, B)라는 칸으로 이동했을 때, 다시 상하좌우로 이동해보면서 몇 번 이동이 가능한지 다시 구할 필요 없이, 예전 방문 때 4번 이동이 가능했다고 저장한 걸 꺼내서 쓰면 1 + 4로 (C, D) 기준 5번 이동할 수 있음을 알 수 있다.

DFS로 특정 칸수에서 몇 번 이동이 가능한지 구하고, 추후 이 점을 다시 방문했을때 다시 DFS로 계산할 필요 없이 이동 횟수를 꺼내서 기억할 수 있도록 해당 칸의 배열에 최대 이동 가능 횟수를 적어서 효율적으로 문제를 해결할 수 있다.

소스 코드

#include <iostream>
#include <string>
using namespace std;

bool visit[50][50];
int dp[50][50];
int board[50][50];
int N, M;

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

int DFS(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= M || board[x][y] <= 0) return 0;
    if (visit[x][y]) {
        cout << -1 << '\n';
        exit(0); // 사이클 탐지하면 출력하고 프로그램 종료
    }
    if (dp[x][y] != -1) return dp[x][y];

    visit[x][y] = true;
    dp[x][y] = 0;

    for (int i = 0; i < 4; i++) {
        int nx = x + (board[x][y] * dx[i]);
        int ny = y + (board[x][y] * dy[i]);
        dp[x][y] = max(dp[x][y], DFS(nx, ny) + 1);
    }

    visit[x][y] = false;
    return dp[x][y];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        string S; cin >> S;
        for (int j = 0; j < S.length(); j++) {
            if (S[j] == 'H') board[i][j] = -1;
            else board[i][j] = S[j] - '0';
        }

        for (int j = 0; j < M; j++) {
            dp[i][j] = -1;
        }
    }
    int answer = DFS(0, 0);
    cout << answer;

    return 0;
}