백준 1937번: 욕심쟁이 판다

문제 설명

• https://www.acmicpc.net/problem/1937
• NxN배열에서 가장 긴 증가하는 수열의 길이를 구하는 것과 동일합니다.

접근법

• DFS와 DP를 함께 사용해야 합니다.
  • DFS탐색을 하다가 DP가 채워진 곳에서는 더이상 탐색하지 않고 DP에 저장된 값을 활용합니다.

DFS 기본

public static int void(int x, int y){
	v[x][y] = true;
	for(int d = 0; d < 4; d++){
    	int nx = x+dx[d];
        int ny = y+dy[d];
        if(true){
        	DFS(nx,ny);
        }
    }

}

정답

import java.util.*;

public class Main {
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int N;
	static int MaxVal = Integer.MIN_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		int[][] board = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}

		int[][] dp = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				MaxVal = Math.max(MaxVal,DFS(new int[] {i,j},board,dp));
			}
		}
		System.out.println(MaxVal);

	}

	public static int DFS(int[] start, int[][] board, int[][] dp) {
		if (dp[start[0]][start[1]] != 0) { // 이미 도착해본 곳이면
			return dp[start[0]][start[1]];
		}
		// 처음 도착하는 곳이면
		dp[start[0]][start[1]] = 1;

		for (int d = 0; d < 4; d++) {
			int nx = start[0] + dx[d];
			int ny = start[1] + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < N && board[start[0]][start[1]] < board[nx][ny]) {
				dp[start[0]][start[1]] = Math.max(dp[start[0]][start[1]], DFS(new int[] { nx, ny }, board, dp) + 1);
			}
		}

		return dp[start[0]][start[1]];
	}

}

비슷한 문제

내리막 길 | 풀이