인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

제가 작성한 아래의 코드에서 항상 실제 답보다 1이 작게 나오는데 그 이유를 알 수 있을까요?

#include <bits/stdc++.h>
using namespace std;

int n, m, ny, nx;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

int mp[51][51];
int dp[51][51];  // 2차원 dp 배열로 수정

// dp[y][x]: 현재 위치에서 최대 몇 번 이동할 수 있는가?
int move(int y, int x) {
    // 이미 계산된 값이 있으면 그 값을 반환
    if (dp[y][x] != -1) return dp[y][x];

    dp[y][x] = 0;  // 이동 불가능한 상태로 설정 (기본값)

    // 4방향 탐색
    for (int i = 0; i < 4; i++) {
        ny = y + mp[y][x] * dy[i];
        nx = x + mp[y][x] * dx[i];

        // 오버플로우 처리 및 구멍 처리
        if (ny >= n || nx >= m || ny < 0 || nx < 0 || mp[ny][nx] == 0) continue;

        int ret = move(ny, nx);
        dp[y][x] = max(dp[y][x], ret + 1);  // 현재 위치에서 한 번 이동하고 나서 계산
    }

    return dp[y][x];
}
int main() {
    cin >> n >> m;

    // 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char v;
            cin >> v;
            if (v == 'H') {
                mp[i][j] = 0;  // 'H'는 구멍이므로 0으로 처리
            } else {
                mp[i][j] = v - '0';  // 숫자는 변환해서 저장
            }
        }
    }

    // DP 테이블 초기화 (-1로)
    memset(dp, -1, sizeof(dp));

    // 배열 처리 확인
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << mp[i][j] << " ";
             cout << dp[i][j] << " ";
        }
        cout << "\n";
    }

    // 첫 위치에서 최대 이동 횟수 계산
    int result = move(0, 0);
    cout << result << "\n";
    
   

    return 0;
}