[TIL_Carrotww] 104 - 23/03/07

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 leetcode 329 - logestincreasingpath - hard

좌표에서 해당 숫자가 크면 해당 자리로 가고를 반복하며 가장 긴 길이를 찾는 문제이다
문제 자체를 보면 dfs로 간단하게 풀릴 것 같다.
맞다.
간단하게 풀린다.
그런데 속도가 너무 느리다.

• 첫 번째 dfs 풀이

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        result = []
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
        def dfs(x, y, val, cnt):
            for i in range(4):
                n_x, n_y = dx[i]+x, dy[i]+y
                if 0 <= n_x and n_x < len(matrix) and 0 <= n_y and n_y < len(matrix[0]):
                    n_val = matrix[n_x][n_y]
                    if val < n_val and dp[n_x][n_y] < cnt+1:
                        dp[n_x][n_y] = cnt + 1
                        dfs(n_x, n_y, n_val, cnt+1)

            result.append(cnt)

        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if dp[i][j] == 0:
                    dfs(i, j, matrix[i][j], 1)

        return max(result)

전형적인 dfs 풀이이다.

하지만 속도가 형편없이 나온다.
이걸 어떻게 개선하나 생각을 해보다가 dp로 풀면 되겠다는 생각이 들었다.
한 자리에서 최대로 갈 수 있는 길이는 어차피 정해져 있으니 그걸 기록하면 되는 것이다.
처음에 꼬여서 코드를 짜는데 오래 걸렸지만 dp를 적용하기에는 쉬운 문제라 뭔가...기분이 좋은 문제 같다 ㅎㅎ

• 두 번째 풀이 dfs + dp

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        row, col = len(matrix[0]), len(matrix)
        dp = [[0] * row for _ in range(col)]
        dc, dr = [1, -1, 0, 0], [0, 0, -1, 1]
        result = 0

        def dfs(c, r):
            if dp[c][r] != 0:
                return dp[c][r]

            temp = [0]
            for i in range(4):
                n_c, n_r = dc[i]+c, dr[i]+r
                if n_c >= 0 and n_r >= 0 and n_c < col and n_r < row and matrix[c][r] < matrix[n_c][n_r]:
                    temp.append(dfs(n_c, n_r))

            dp[c][r] = max(temp) + 1

            return dp[c][r]
        for c in range(col):
            for r in range(row):
                result = max(result, dfs(c, r))

        return result

추가로 다른 문제도 풀려고 했는데 못 풀어서 내일... 다시 풀어서 올려야겠다.