[백준 1937] 욕심쟁이 판다

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

난이도: G3

카테고리: DP, DFS

Problem

1. n x n 맵에 자연수가 채워져있다.

2. 이중, 상,하,좌,우로 이동하여 가는 경로중 자연수가 커지게 갈 수 있는 가장 긴 경로의 길이를 구하면 된다.

Idea

단순히 DP를 쓰기엔 상하좌우를 모두 움직일 수 있기 때문에, DFS를 통해 각 지점을 탐색하며 DP를 작성해 나가야 한다.

dp에는 그 칸에서 갈 수 있는 최대 경로 길이가 담기게 된다. 만약 갈 수 있는 경로가 없다면, 1을 저장한다. (한칸의 길이는 1이기 때문)

Solution

package week27_DynamicProgramming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main_1937_G3_욕심쟁이판다_김태수 {
    static int map[][], dp[][],N, ans;
    static int[][] direction = {
        {1,0},
        {0,1},
        {-1,0},
        {0,-1}
    };
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ans = 1;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new int[N][N];
        StringTokenizer st = null;
        for(int i = 0 ; i < N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.fill(dp[i],-1);
        }

        for(int i = 0 ; i < N;i++){
            for(int j = 0 ; j < N ;j++){
                if(dp[i][j] == -1) dfs(i,j);
            }
        }
        System.out.println(ans);
        
    }

    public static int dfs(int i, int j){
        if(dp[i][j] != -1) return dp[i][j];
        dp[i][j] = 1;
        for(int[] dir: direction){
            int nx = dir[0] + i;
            int ny = dir[1] + j;
            if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if(map[i][j] < map[nx][ny]){
            	//상하좌우의 dp값 + 자기사진
                int cnt = dfs(nx,ny) + 1;
                dp[i][j] = Math.max(dp[i][j], cnt);
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return dp[i][j];
    }
}