백준 1937번

문제

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

알고리즘

1. dp

2. dfs

풀이 

1. 경로를 끝까지 따라간다.

• 어떤 좌표에서 시작했을 때, 갈 수 있는 모든 경로를 탐색해야 하므로 DFS가 적합
• DFS를 통해 끝까지 이동하고, 더 이상 이동할 수 없을 때 경로 길이를 1로 시작해서 거꾸로 누적

2. 중복 계산 방지

• (x,y)에서 시작한 최대 경로 길이를 dp[x][y]에 저장
• 이미 계산한 좌표는 다시 DFS를 돌리지 않고 바로 값 반환

3. 예시 

map[1][1] = 11
→ 이동 가능한 방향: (2,1) = 15
→ DFS 호출: dfs(2,1)
    map[2][1] = 15
    → 이동 가능한 방향: (3,2) = 16
    → DFS 호출: dfs(3,2)
        map[3][2] = 16
        → 이동 불가 → dp[3][2] = 1
    ← 돌아오면서 dp[2][1] = dp[3][2] + 1 = 2
← 다시 돌아오며 dp[1][1] = dp[2][1] + 1 = 3

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	static int[][] move = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	static int n;
	static List<int[]> map;
	static int max = Integer.MIN_VALUE;
	static int[][] dp;

	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			n = Integer.parseInt(br.readLine());
			map = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
				map.add(s);
			}
			dp = new int[n][n];

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					max = Math.max(dfs(i, j), max);
				}
			}
			System.out.println(max);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	static int dfs(int x, int y) {
		if (dp[x][y] != 0)
			return dp[x][y];

		dp[x][y] = 1;
		for (int[] ints : move) {
			int nx = x + ints[0];
			int ny = y + ints[1];

			if (nx < 0 || nx >= n || ny < 0 || ny >= n || map.get(nx)[ny] <= map.get(x)[y]) {
				continue;
			}
			dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
		}
		return dp[x][y];
	}
}