[파이썬/Python] Leet Code 3459(Hard): Length of Longest V-Shaped Diagonal Segment

숨·2025년 8월 27일

코테

알고리즘 문제 풀이

목록 보기

122/128

📌 문제 : Leet Code 3459

📌 문제 탐색하기

grid : 0, 1, 2를 담고 있는 2차원 행렬 ( $1 ≤ grid.length, grid[i].length ≤ 500$ )

문제 풀이

n x m 크기의 2차원 행렬 grid는 0 또는 1 또는 2라는 정수가 담겨 있다.

특정 규칙과 조건에 따라 만들 수 있는 V-shaped diagonal segment의 최대 길이를 구하는 문제이다.

V-shaped diagonal segment이란?

1로 시작해서 후속 요소들이 2, 0, 2, 0, ..이란 패턴을 따라 이동
같은 대각선 방향으로 지속적으로 움직임
단, 한번은 꼭 시계방향으로 90도 움직인 방향으로 이동해야 함
없으면 0을 반환

이 문제는 위치, 방향, 턴 여부, 다음 기대값이란 다양한 복합 상태를 보존하면서 최대 길이를 구해야 한다.

그냥 DFS/BFS만 사용한다면 시간 초과 에러가 발생한다.
따라서, 중복 상태를 재사용할 수 있도록 DP(메모이제이션) 방식을 함께 적용해야 한다.
→ DFS로 모든 경로 탐색 & 중복 상태는 메모이제이션으로 재사용해 효율 상승

1️⃣ DFS

각 상태별 최대 길이 리턴
계산된 값은 캐시에 저장해 중복 계산 방지

2️⃣ 메모이제이션

@lru_cache(None)
- Python의 내장 메모이제이션(캐싱) 도구
- 함수 호출 시 동일한 인자에 대해 한번 계산한 결과 저장
동일 파라미터로 dfs 호출 시 저장된 결과 즉시 반환
DP와 메모제이션 관계
- DP → 문제 해결 전략
  - 문제를 작은 하위 문제로 나누고 각 하위 문제의 해답 조합해 전체 문제 해결
- 메모이제이션 → DP 전략 구현하기 위한 기법
  - 탑다운 방식의 DP, 재귀 호출 결과 저장해 중복 계산 피하기

가능한 시간복잡도

DFS + 메모이제이션 → $O(n×m×4×2×2) = O(nm)$
DFS 내 이동 → $O(1)$

최종 시간복잡도
최악의 경우 $O(nm) = O(250000)$ 이므로 충분히 동작할 수 있다.

알고리즘 선택

DFS + 메모이제이션

📌 코드 설계하기

이동 방향 정의
DFS 정의
2-1. 범위 확인 및 패턴 확인
2-2. 기대값 변경
2-3. 방향 변경 없이 직진 이동
2-4. 턴 여부 파악해 1번 턴 수행
전체 grid에서 시작점 찾아 DFS 수행

📌 시도 회차 수정 사항

1회차

패턴에 맞는 길을 찾아내는 것이라 생각해서 BFS를 활용하려 했는데 조건에 따라 구현하는 것도 너무 어렵고 구현해서 돌렸을 때 시간 초과 에러가 발생했다.
구현한 방식으로 하면 4가지 방향으로의 탐색 뿐 아니라 경로 길이에 따라서도 연산량이 너무 많아졌다. 이 문제가 최단 거리를 찾는게 아니라 최대한 많은 길이를 찾는 것이 중점이기 때문에 BFS만을 사용하는 것은 안맞았던 것 같다.

📌 정답 코드

class Solution:
    def lenOfVDiagonal(self, grid):
        n, m = len(grid), len(grid[0])
        dx = [1, 1, -1, -1]
        dy = [1, -1, -1, 1]

        from functools import lru_cache
        
        # DFS + 메모이제이션 함수
        # x, y 위치, 방향 d, 턴 사용 여부 turn(0/1), next 기대값(2 또는 0)
        @lru_cache(None)
        def dfs(x, y, d, turn, next_val):
            # 범위 벗어나거나 패턴 불일치 시 0 반환
            if not (0 <= x < n and 0 <= y < m) or grid[x][y] != next_val:
                return 0

            # 다음 기대값 토글(2 <-> 0)
            next_expect = 0 if next_val == 2 else 2

            res = 0
            # 직진
            res = max(res, 1 + dfs(x + dx[d], y + dy[d], d, turn, next_expect))

            # 턴 가능하면 한 번 턴
            if turn == 0:
                nd = (d + 1) % 4  # 시계 방향으로 한 번 턴
                res = max(res, 1 + dfs(x + dx[nd], y + dy[nd], nd, 1, next_expect))
            return res

        max_len = 0
        # 시작점은 grid[i][j] == 1이고, next_val은 2부터 시작
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    for d in range(4):
                        max_len = max(max_len, 1 + dfs(i + dx[d], j + dy[d], d, 0, 2))
        return max_len

결과

👍 다른 풀이

class Solution:
    def lenOfVDiagonal(self, grid: List[List[int]]) -> int:
        # Dynamic Programming
        # Let dp(x, y, t, d) be the longest segment starting with (x, y) where the segment has been turned or not (indicated by the binary flag t) and the current direction is d.
        # When grid(x, y) == 1:
        # dp(x, y, t, *) = max(dp(x', y', true, d) if grid(x', y') == 2, 1)
        # Otherwise:
        # dp(x, y, t, d) = max(dp(x', y', t, d) if grid(x',y') == 2 - grid(x, y) else 1, dp(x'', y'', false, d') if d is true and grid(x'',y'') == 2 - grid(x, y))
        # The overall complexity is O(m * n * 4 * 2) ~ O(2 * 10^6).
        
        # 방향 벡터는 네 가지 대각선 방향을 의미
        dirs = [(1, 1), (1, -1), (-1, -1), (-1, 1)]
        n = len(grid)
        m = len(grid[0])
        
        # 다음 기대값을 담은 배열. 인덱스는 현재칸의 값(grid[x][y])이고, 값은 해당 칸 이후에 와야 할 숫자를 뜻한다
        nv = [2, 2, 0] # Next expected value
		
        # helper 함수는 재귀로 최대 길이를 찾는데, 캐시를 사용해 중복 상태를 저장해 계산 속도를 높인다.
        # x, y: 현재 위치 좌표
        # turned: 90도 방향 전환을 했는지 여부 (True/False)
        # dir: 현재 이동 방향 인덱스 (dirs 배열에서 0~3)
        @functools.cache
        def helper(x, y, turned, dir):
            # First, we do not change the direction
            
            # 최소 길이 
            res = 1
            dx, dy = dirs[dir]
            if 0 <= x + dx < n and 0 <= y + dy < m and grid[x + dx][y + dy] == nv[grid[x][y]]:
                res = helper(x + dirs[dir][0], y + dirs[dir][1], turned, dir) + 1
            if not turned:
                dx, dy = dirs[(dir + 1) % 4]
                if 0 <= x + dx < n and 0 <= y + dy < m and grid[x + dx][y + dy] == nv[grid[x][y]]:
                    res = max(res, helper(x + dx, y + dy, True, (dir + 1) % 4) + 1)
            return res

        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    # Optimization: we can compute the theorically longest path. If the current answer is already better than this, we do not need to make the DFS.
                    # 최적화: 이론상 최장 경로 길이 추정 후 탐색 생략 가능
                    tm = (n - i, j + 1, i + 1, m - j)
                    for d in range(4):
                    	# 이론상 최대 길이가 지금까지 구한 답보다 크면 탐색
                        if tm[d] > ans:
                            ans = max(ans, helper(i, j, False, d))
        return ans

Runtime : 748ms
DFS와 DP를 결합한 방법