문제 푼 날짜 : 2021-10-01

문제

문제 링크 : https://www.acmicpc.net/problem/1937

접근 및 풀이

DP와 DFS를 이용한 그래프 탐색문제이다.
문제에 입력으로 주어진 대나무 숲 모든 위치에 판다를 놓아보면서 판다가 얼마나 이동할 수 있는지 확인하고 최댓값을 구해주었다.
탐색하면서 중요한건 메모이제이션을 활용하는 것이다. 이를 위해 dp 배열을 선언하였고, dp배열이 의미하는 것은 해당 인덱스에 판다를 놓았을 때, 얼마나 이동할 수 있는지이다.
이를 이용하여 탐색하면서 dp 배열을 업데이트시켜주었다.
탐색할 때 중요한 것은 이동할 곳의 대나무가 현재 위치보다 많은지 체크해주는 것이다.

코드

// 백준 1937번 : 욕심쟁이 판다
#include <iostream>
#include <cstring>

using namespace std;

int n;
int bamboo[501][501];
int dp[501][501];
int d[4][2] = {{ -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }};

int dfs(int y, int x) {
    int &ret = dp[y][x];
    if (ret != -1) {
        return ret;
    }
    ret = 1;
    for (int i = 0; i < 4; i++) {
        int nextY = y + d[i][0];
        int nextX = x + d[i][1];
        
        if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= n) {
            continue;
        }
        if (bamboo[y][x] < bamboo[nextY][nextX]) {
            ret = max(ret, dfs(nextY, nextX) + 1);
        }
    }
    return ret;
}

int main() {
    cin >> n;
    int ans = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> bamboo[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans, dfs(i, j));
        }
    }
    cout << ans;
    return 0;
}

결과

피드백

예전에 풀어봤었는데, DP 공부하면서 다시 한 번 풀어보았다.
DP는 언제 익숙해질까...