Longest Increasing Path in a Matrix
LeetCode 329번 문제.
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
Longest Increasing Path in a Matrix - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
1. 문제
Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
주어진 배열에서 가장 큰 길이의 증가하는 경로를 찾으라는 문제.
Example 1:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
Example 3:
Input: matrix = [[1]]
Output: 1
Constraints:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 231 - 1
2. 풀이
■ 풀이 방법
dfs를 사용해서 각 원소마다 모든 경로를 탐색하면 주어진 조건상 시간 초과가 걸린다.
때문에 해당 문제는 다른 방법으로 접근이 필요하다.
문제의 Example2를 다시 보자.
첫 번째 원소인(0, 0) 3에서 가장 긴 증가하는 경로의 길이는 어떻게 정해질까?
경로의 원소는 "증가"해야 하기 때문에 '3' 다음이 될 수 있는 원소는 (0, 1)의 '4' 밖에 없다.
즉 이경우 다음이 성립한다.
첫 번째 원소에서 시작하는 가장 긴 증가하는 경로의 길이 = (0, 1) 에서 시작하는 가장 긴 증가하는 경로의 길이 + 1
(0, 1)일 때도 위와 같은 방법으로 가장 긴 증가하는 경로의 길이를 구할 수 있다.
(0, 1) 에서 시작하는 가장 긴 증가하는 경로의 길이 = (0, 2) 에서 시작하는 가장 긴 증가하는 경로의 길이 + 1
그렇다면 이번에는 (1, 1)의 원소인 '2'를 보자, (1, 1)과 인접하면서 '2' 보다 큰 원소는 (1, 0), (0, 1), (1, 2) 세 가지다.
즉, (1, 1) 다음에 올 수 있는 원소는 위의 세 가지라는 뜻이 된다.
따라서 (1, 1) 에서 시작하는 가장 긴 증가하는 경로의 길이는 다음과 같다.
(1, 1) 에서 시작하는 가장 긴 증가하는 경로의 길이 = Max((1, 0) 에서 시작하는 가장 긴 증가하는 경로의 길이, (0, 1) 에서 시작하는 가장 긴 증가하는 경로의 길이, (1, 2) 에서 시작하는 가장 긴 증가하는 경로의 길이) + 1
이를 일반화하면 다음과 같다.
(r, c) 에서 시작하는 가장 긴 증가하는 경로의 길이 = Max((r,c)다음으로 올 수 있는 원소에서 시작하는 가장 긴 증가하는 경로의 길이)) + 1
위와 같은 점화식을 세울 수 있으므로 해당 문제는 dp를 사용해서 풀 수 있다.
■ code
□ staticField
int[][] memo; //[1]
int[] rowSet = {0, -1, 0, 1}; //[2]
int[] colSet = {1, 0, -1, 0};● [1] : 각 원소에서 시작하는 가장 긴 증가하는 경로의 길이를 저장하는 배열
● [2] : index에 따라 원소의 상하좌우를 결정하는 데 사용되는 배열
□ longestIncreasingPath
가장 긴 증가하는 경로의 길이를 찾는 메서드
각 원소마다 dp를 사용해 [해당 원소에서 시작하는 가장 긴 증가하는 경로의 길이]를 구한다.
[longestIncreasingPath]
public int longestIncreasingPath(int[][] matrix) {
memo = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) { //[1]
for (int j = 0; j < matrix[0].length; j++) {
dp(matrix, i, j);
}
}
return Arrays.stream(d) //[2]
.flatMapToInt(Arrays::stream)
.max()
.getAsInt();
}● [1] : 각 원소마다 dp를 사용해 해당 원소에서 시작하는 가장 긴 증가하는 경로의 길이를 구하고 memo에 저장한다.
● [2] : memo에서 가장 큰 값을 반환(=> 주어진 배열에서 가장 긴 증가하는 경로의 길이)
□ dp
주어진 원소에서 시작하는 가장 긴 증가하는 경로의 길이를 구하는 메서드
[dp]
private void dp(int[][] matrix, int row, int col) {
int result = 1; //[1]
if (memo[row][col] != 0) { //[2]
return;
}
for (int i = 0; i < 4; i++) {
int nextRow = row + rowSet[i];
int nextCol = col + colSet[i];
if (nextRow < 0 || nextRow >= matrix.length || nextCol < 0 || nextCol >= matrix[0].length
|| matrix[nextRow][nextCol] <= matrix[row][col]) { //[3]
continue;
}
int dpResult = dp(matrix, nextRow, nextCol) + 1; //[4]
if (dpResult > result) { //[5]
result = dpResult;
}
}
memo[row][col] = result; //[6]
}● [1] : 가장 긴 증가하는 경로의 길이가 담길 변수. 기본값은 1(=문제에서 각 원소 자체의 길이를 1로 보기 때문)
● [2] : 이미 해당 원소에서 시작하는 가장 긴 증가하는 경로의 길이가 있다면 메서드를 빠져나온다.
● [3] : 주어진 원소의 다음에 올 수 있는 원소를 찾는 조건문(배열의 경계를 벗어났는지, 다음에 올 원소가 증가하는지)
● [4] : 주어진 원소의 다음에 올 수 있는 원소에서 시작하는 가장 긴 증가하는 경로의 길이를 구한다.
● [5] : 구해진 경로의 길이와 result값을 비교해서 반복문을 돌며 최댓값으로 갱신한다.
● [6] : 해당 원소에서 시작하는 가장 긴 증가하는 경로의 길이를 meme에 저장.
■ 전체 코드
[전체 코드]
import java.util.Arrays;
public class Solution {
int[][] memo;
int[] rowSet = {0, -1, 0, 1};
int[] colSet = {1, 0, -1, 0};
private void dp(int[][] matrix, int row, int col) {
int result = 1;
if (memo[row][col] != 0) {
return;
}
for (int i = 0; i < 4; i++) {
int nextRow = row + rowSet[i];
int nextCol = col + colSet[i];
if (nextRow < 0 || nextRow >= matrix.length || nextCol < 0 || nextCol >= matrix[0].length
|| matrix[nextRow][nextCol] <= matrix[row][col]) {
continue;
}
int dpResult = dp(matrix, nextRow, nextCol) + 1;
if (dpResult > result) {
result = dpResult;
}
}
memo[row][col] = result;
}
public int longestIncreasingPath(int[][] matrix) {
memo = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
dfs(matrix, i, j);
}
}
return Arrays.stream(d)
.flatMapToInt(Arrays::stream)
.max()
.getAsInt();
}
}
3. 특이 사항
■ BFS
처음에 '거리'와 관련된 문제이길래 냅다 BFS를 적용했지만 전혀 다른 문제였다.
■ DFS
DFS를 적용해서 각 원소에서 모든 경로를 구한 뒤 최댓값을 구했지만 시간 초과
위와 같은 실수를 한 이유를 지금 생각해보면 문제에서 배열을 쓰고 '경로'에 관한 문제라 bfs, dfs를 사용해야 된다고 확정해버려서 인 것 같다. 너무 bfs, dfs에 의존하지 말고 문제를 잘 분석할 필요를 느꼈다.
댓글