[medium] 240. Search a 2D Matrix II

문제

https://leetcode.com/problems/search-a-2d-matrix-ii/

Search a 2D Matrix II - LeetCode

---

풀이방법

문제 보자마자 DFS로 중복방문 하지 않도록 하면서 풀면 되겠다는 생각이 들었다

1. [0,0] 위치부터 DFS 탐색을 시작한다

2. 탐색은 아래 과정을 반복한다

    - 방문했던 곳이면 패스하고, 방문하지 않았던 곳이면 visited 를 True로 바꾸고 해당지점의 숫자와 target 값을 비교한다

    - target 값보다 작으면 (row+1, col) 과 (row,col+1) 지점을 탐색하고, target 값보다 크면 (row-1, col) 과 (row,col-1) 지점을 탐색한다. target 값과 일치하면 True 리턴하고 탐색 중단

시간복잡도와 공간복잡도 모두 O(M*N)

반응형

---

코드

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        M = len(matrix)
        N = len(matrix[0])
        visited = [[False] * N for m in range(M)]
        
        def dfs(row, col, visited):
            if row<0 or row>=M or col<0 or col>=N:
                return False
            if visited[row][col]:
                return False
            visited[row][col] = True
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                if dfs(row+1, col, visited):
                    return True
                if dfs(row, col+1, visited):
                    return True
            elif matrix[row][col] > target:
                if dfs(row-1, col, visited):
                    return True
                if dfs(row, col-1, visited):
                    return True			
            return False

        return dfs(0, 0, visited)