[리트코드] 2267 - Check if There Is a Valid Parentheses String Path

2267. Check if There Is a Valid Parentheses String Path

Hard

---

A parentheses string is a non-empty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

• It is ().
• It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
• It can be written as (A), where A is a valid parentheses string.

You are given an m x n matrix of parentheses grid. A valid parentheses string path in the grid is a path satisfying all of the following conditions:

• The path starts from the upper left cell (0, 0).
• The path ends at the bottom-right cell (m - 1, n - 1).
• The path only ever moves down or right.
• The resulting parentheses string formed by the path is valid.

Return true if there exists a valid parentheses string path in the grid. Otherwise, return false.

 

Example 1:

Input: grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
Output: true
Explanation: The above diagram shows two possible paths that form valid parentheses strings.
The first path shown results in the valid parentheses string "()(())".
The second path shown results in the valid parentheses string "((()))".
Note that there may be other valid parentheses string paths.

Example 2:

Input: grid = [[")",")"],["(","("]]
Output: false
Explanation: The two possible paths form the parentheses strings "))(" and ")((". Since neither of them are valid parentheses strings, we return false.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] is either '(' or ')'.

분류

배열, 동적 계획법, 행렬, Bracket Sequences

---

문제 풀이

문제 분석

이 문제는 m x n 크기의 격자(grid)에서 좌측 상단 (0, 0)에서 우측 하단 (m-1, n-1)까지 오른쪽 또는 아래쪽으로만 이동하며 경로를 만들 때, 그 경로상의 괄호 문자열이 **올바른 괄호 문자열(Valid Parentheses String)**이 되는지 여부를 판단하는 문제입니다.

• 입력: '(' 또는 ')'로 이루어진 2차원 리스트 grid
• 출력: 유효한 경로가 존재하면 True, 없으면 False
• 제약 조건:
  • 경로는 (0,0)에서 시작하여 (m-1, n-1)에서 끝나야 함.
  • 이동은 오른쪽, 아래쪽만 가능.
  • 괄호 문자열이 유효하려면 여는 괄호 (와 닫는 괄호 )의 개수가 같고, 어떤 접두사에서도 닫는 괄호의 개수가 여는 괄호의 개수를 초과하지 않아야 함.

---

접근 방법

이 문제는 **너비 우선 탐색(BFS)**과 **상태 압축(State Compression)**을 활용하여 해결합니다.

• BFS 선택 이유: 격자에서 최단 경로를 찾는 문제가 아니라 존재 여부를 찾는 문제이며, 상태(현재 위치, 현재까지의 괄호 균형)를 큐에 담아 탐색하기에 적합합니다. DFS(재귀)도 가능하지만 파이썬의 재귀 깊이 제한이나 스택 오버플로우 가능성을 고려해 BFS(큐)가 더 안전합니다.
• 상태 정의: 단순히 방문한 좌표 (x, y)만으로는 부족합니다. 같은 좌표에 도달하더라도 **현재까지 쌓인 여는 괄호의 개수(균형, balance/cnt)**가 다르면 이후 경로의 유효성이 달라지기 때문입니다. 따라서 상태를 (x, y, cnt)로 정의합니다. cnt는 현재까지 (의 개수에서 )의 개수를 뺀 값(열린 괄호의 수)입니다.
• 가지치기(Pruning) & 방문 체크:
  • cnt가 음수가 되면 유효하지 않은 문자열이므로 탐색 중단.
  • 도착 지점 (n-1, m-1)에 도달했을 때 cnt == 0이어야 유효함.
  • visited 집합에 (x, y, cnt)를 저장하여 동일한 상태의 중복 탐색을 방지합니다. 이는 시간 복잡도를 보장하는 핵심입니다.

---

구현 설명

1. 초기 검증 및 초기화

코드는 시작 전 명백히 불가능한 경우를 빠르게 걸러냅니다.

• 시작점 (0,0)이 )이면 절대 올바른 문자열이 될 수 없으므로 False 반환.
• 도착점 (n-1, m-1)이 (이면 마지막에 닫히지 않은 괄호가 남으므로 False 반환.
• BFS를 위한 큐(deque)를 생성하고 시작 상태 (0, 0, 1)을 넣습니다. 시작이 (이므로 초기 cnt는 1입니다.
• 방문 기록용 visited 집합에 시작 상태를 추가합니다.

2. BFS 탐색 루프

큐가 빌 때까지 반복하며 상태를 확장합니다.

• 큐에서 현재 상태 (x, y, cnt)를 꺼냅니다.
• 도착 조건 확인: 현재 위치가 도착점 (n-1, m-1)이고 cnt == 0이면 유효한 경로를 찾은 것이므로 즉시 True 반환.

3. 다음 상태 생성 및 유효성 검사

현재 위치에서 오른쪽((0, 1)), 아래쪽((1, 0))으로 이동을 시도합니다.

• 격자 범위 확인: 0 <= sx < n, 0 <= sy < m 인지 확인.
• 다음 칸이 ( 인 경우:
  • cnt가 1 증가합니다 (cnt + 1).
  • 새로운 상태 (sx, sy, cnt+1)가 visited에 없으면 큐에 추가하고 방문 처리.
• 다음 칸이 ) 인 경우:
  • 중요: cnt > 0일 때만 이동 가능합니다. cnt가 0인데 )를 만나면 접두사 조건 위반(닫는 괄호 과다)이므로 탐색하지 않습니다.
  • cnt가 1 감소합니다 (cnt - 1).
  • 새로운 상태 (sx, sy, cnt-1)가 visited에 없으면 큐에 추가하고 방문 처리.

4. 탐색 종료

큐가 비워질 때까지 도착 조건을 만족하는 상태를 찾지 못하면 False를 반환합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(m * n * (m + n))

  • 격자의 크기는 m * n입니다.
  • 각 셀에서 가능한 cnt(균형)의 최댓값은 경로의 최대 길이인 m + n - 1입니다. (전부 (인 경우)
  • 따라서 가능한 전체 상태의 수는 O(m * n * (m + n))입니다.
  • 각 상태는 visited 집합 덕분에 최대 한 번만 처리되므로 총 연산 횟수는 상태의 수에 비례합니다.

• 공간 복잡도: O(m * n * (m + n))

  • visited 집합과 큐에 저장되는 최대 상태의 수가 위와 동일하기 때문입니다.

---

핵심 포인트

1. 상태에 '균형(cnt)' 포함하기: 좌표만으로는 부족하며, 현재까지 유효한 괄호 문자열을 유지하기 위한 '열린 괄호의 수(cnt)'를 상태에 반드시 포함해야 합니다.
2. 조기 종료 조건 활용: 시작/끝 문자가 잘못된 경우(시작: ), 끝: () 즉시 False를 반환하고, 탐색 중 cnt < 0이 되는 경우를 배제하여 불필요한 연산을 줄입니다.
3. 방문 배열/집합의 차원 확장: 일반적인 2차원 방문 배열이 아닌 (x, y, cnt) 3차원 상태 공간에 대한 방문 체크(visited set)를 통해 중복 탐색을 방지하고 다항 시간 복잡도를 보장합니다.

풀이 코드

from collections import deque

class Solution:
    def hasValidPath(self, grid: list[list[str]]) -> bool:
        n = len(grid)
        m = len(grid[0])
        if grid[0][0] == ")" or grid[n-1][m-1] == "(":
            return False

        queue = deque()
        queue.append((0,0,1))

        visited = set()

        directions = [(1,0),(0,1)]
        while queue:
            x,y,cnt = queue.popleft()
            
            if x == n-1 and y == m-1 and cnt == 0:
                return True

            for dx,dy in directions:
                sx,sy = x+dx,y+dy
                if 0<=sx<n and 0<=sy<m:
                    if grid[sx][sy] =="(" and not (sx,sy,cnt + 1) in visited:
                        queue.append((sx,sy,cnt+1))
                        visited.add((sx,sy,cnt+1))

                    elif grid[sx][sy] == ")" and cnt > 0 and not (sx,sy,cnt-1) in visited:
                        queue.append((sx,sy,cnt-1))
                        visited.add((sx,sy,cnt-1))
                        
        return False