leetcode: Longest Increasing Path in a Matrix

먼저, 브루트포스로 모든 점에 대해 DFS를 돌려 가장 긴 path를 찾는 방법이 있을 것이다. 하지만 이 방법의 경우 시간초과가 발생한다.

class Solution {
	public static int[] dr = { 1, -1, 0, 0 };
	public static int[] dc = { 0, 0, 1, -1 };

	public int longestIncreasingPath(int[][] matrix) {
		if (matrix.length == 0) {
			return 0;
		}

		int maxRow = matrix.length;
		int maxCol = matrix[0].length;

		int answer = 0;
		for (int i = 0; i < maxRow; ++i)
			for (int j = 0; j < maxCol; ++j)
				answer = Math.max(answer, dfs(matrix, i, j, maxRow, maxCol));
		return answer;
	}

	private int dfs(int[][] matrix, int row, int col, int maxRow, int maxCol) {
		int ans = 0;
		for (int i = 0; i < 4; i++) {
			int r = row + dr[i];
			int c = col + dc[i];
			if (isBoundary(r, c, maxRow, maxCol) && matrix[r][c] > matrix[row][col]) {
				ans = Math.max(ans, dfs(matrix, r, c, maxRow, maxCol));
			}
		}
		return ++ans;
	}

	public boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow || col >= maxCol) {
			return false;
		}
		return true;
	}
}

 

 

위 코드에서 시간을 줄일 수 있는 부분은 어디일까? 위 코드에서 중복되는 부분은 dfs로 계산하여 max를 업데이트 하는 부분이다.

이 부분을 줄이기 위해 모든 점에 대해 가장 긴 path를 찾는 도중에 이미 갔던 길의 경우는 저장해 두고,

다시 방문할 때 저장했던 길이를 바로 리턴해주면 더 효율적일 것이다. => 메모이제이션

class Solution {
	public static int[] dr = { 1, -1, 0, 0 };
	public static int[] dc = { 0, 0, 1, -1 };

	public int longestIncreasingPath(int[][] matrix) {
		if (matrix.length == 0) {
			return 0;
		}

		int maxRow = matrix.length;
		int maxCol = matrix[0].length;

		int[][] memo = new int[maxRow][maxCol];

		int answer = 0;
		for (int i = 0; i < matrix.length; ++i) {
			for (int j = 0; j < matrix[i].length; ++j) {
				answer = Math.max(answer, dfs(matrix, memo, i, j, maxRow, maxCol));
			}
		}
		return answer;
	}

	public int dfs(int[][] matrix, int[][] memo, int row, int col, int maxRow, int maxCol) {
		if (memo[row][col] != 0) {
			return memo[row][col];
		}

		for (int i = 0; i < 4; i++) {
			int r = row + dr[i];
			int c = col + dc[i];
			if (isBoundary(r, c, maxRow, maxCol) && matrix[r][c] > matrix[row][col]) {
				memo[row][col] = Math.max(memo[row][col], dfs(matrix, memo, r, c, maxRow, maxCol));
			}
		}

		memo[row][col]++;
		return memo[row][col];
	}

	public boolean isBoundary(int row, int col, int maxRow, int maxCol) {
		if (row < 0 || col < 0) {
			return false;
		}
		if (row >= maxRow || col >= maxCol) {
			return false;
		}
		return true;
	}
}