백준 1937번 욕심쟁이 판다

🔒[문제 url]

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

🔑알고리즘

어느 지점을 출발점으로 잡는지에 따라 경로가 달라지므로, 모든 지점을 시작점으로 DFS를 진행하여 경로의 최대값을 찾는다.

깊이 우선 탐색이기때문에, 이미 방문한 지점의 최대 경로값은 갱신되어 있으므로 확인할 필요가 없다. DP

• 각 지점을 시작으로 DFS를 진행하며, visited 배열의 각 지점에 해당 지점으로부터의 최대 경로값을 기록한다.

🐾부분 코드

int DFS(int x, int y)
{
    if (visited[x][y] != -1) return visited[x][y];

    visited[x][y] = 0;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (1 <= nx && nx <= n && 1 <= ny && ny <= n)
        {// Check range
            if (map[x][y] < map[nx][ny])
            {// if next position has more bamboos
                visited[x][y] = max(visited[x][y], DFS(nx, ny));
            }
        }
    }
    // route cnt starts with 1
    return ++visited[x][y];
}

<DFS 함수>
이미 방문한 지점은 다시 탐색하지 않는다.
현재 지점보다 더 많은 대나무가 있는 지점들에 대해 DFS를 진행 후, 가장 큰 값으로 현재 지점을 갱신한다.

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <algorithm>
using namespace std;

int n;
int map[501][501];
int visited[501][501];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; // 상 우 하 좌

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> map[i][j];
            visited[i][j] = -1;
        }
}

int DFS(int x, int y)
{
    if (visited[x][y] != -1) return visited[x][y];

    visited[x][y] = 0;

    for (int i = 0; i < 4; i++)
    {
        int nx = x + dir[i][0], ny = y + dir[i][1];
        if (1 <= nx && nx <= n && 1 <= ny && ny <= n)
        {// Check range
            if (map[x][y] < map[nx][ny])
            {// if next position has more bamboos
                visited[x][y] = max(visited[x][y], DFS(nx, ny));
            }
        }
    }
    //route cnt starts with 1
    return ++visited[x][y];
}

void SOLVE()
{
    int ans = 0;
    // Do DFS on each position
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans = max(ans, DFS(i, j));

    cout << ans;
}


int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

Easy