69. Search a 2D Matrix II

🎯 leetcode - 240. Search a 2D Matrix II

---

📌 문제

- 파이썬 알고리즘 인터뷰 69번 문제

📌 날짜

2020.03.01

📌 시도 횟수

3 try

---

🤔 나의 풀이 1

💡 Code 1 : DFS 재귀

class Solution:
    searched = False

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        visited = set()

        def search(x, y):
            if (
                not self.searched
                and (x, y) not in visited
                and x < len(matrix)
                and x >= 0
                and y >= 0
                and y < len(matrix[0])
            ):
                visited.add((x, y))
                if matrix[x][y] > target:
                    search(x - 1, y)
                    search(x, y - 1)
                elif matrix[x][y] < target:
                    search(x + 1, y)
                    search(x, y + 1)
                else:
                    self.searched = True
                    return

            else:
                return

        search(len(matrix) // 2, len(matrix[0]) // 2)
        return self.searched

💡 문제 해결 방법

- DFS를 복습하고 싶어서 DFS 재귀로 풀었다.
1. 초기 탐색 값은 matrix의 중앙 값으로 주었다. 
(중앙을 처음으로 하는게 평균적으로 빠를 것 같았다.)

2. 만약 이미 탐색한 값이 아니면서 x, y가 범위 안에 있을때,

3. 현재 matrix[x][y]와 target을 비교한다.
> 만약 같다면 클래스 변수 searched를 True로 주고 리턴한다. 
(searched는 한 번 True가 되면 다음 재귀부터는 검사하지 않고 바로 리턴되도록 했다.)
> 만약 target보다 작다면, 현재 행렬 위치를 기준으로 더 큰 값이 있는 위치인
(오른쪽, 아래쪽)을 다음에 검사하도록 x, y를 설정하고 재귀로 호출했다.
> 만약 target보다 크다면, 현재 행렬 위치를 기준으로 더 작은 값이 있는 위치인
(왼쪽, 위쪽)을 다음에 검사하도록 x, y를 설정하고 재귀로 호출했다.

4. 최종적으로 searched를 리턴한다.

---

🤔 나의 풀이 2

💡 Code 2 : DFS 반복문

class Solution:
    searched = False

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        visited = set()
        x, y = len(matrix) // 2, len(matrix[0]) // 2
        stack = deque([[x, y]])

        while stack and not self.searched:
            cur = stack.pop()
            x, y = cur[0], cur[1]
            if (
                (x, y) not in visited
                and x >= 0
                and x < len(matrix)
                and y >= 0
                and y < len(matrix[0])
            ):
                visited.add((x, y))
                if matrix[x][y] > target:
                    stack.append([x - 1, y])
                    stack.append([x, y - 1])
                elif matrix[x][y] < target:
                    stack.append([x + 1, y])
                    stack.append([x, y + 1])
                else:
                    self.searched = True
                    break

        return self.searched

💡 문제 해결 방법

- 위의 과정을 반복문으로 바꾼 것 밖에 없다. 나머지는 동일!
- 반복문으로 구현하기 위해 stack을 사용했다.
- stack을 deque로 구현했다. list보다 deque가 좀 더 빠를 것 같아서...

---

😉 다른 풀이

📌 하나. 첫 행의 맨 뒤에서 차례대로 탐색

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        # 첫 행의 맨 끝
        row, col = 0, len(matrix[0]) - 1

        while row <= len(matrix) - 1 and col >= 0:
            if target == matrix[row][col]:
                return True
            elif target < matrix[row][col]:
                col -= 1
            elif target > matrix[row][col]:
                row += 1

        return False

💡 문제 해결 방법

1. 시작 지점을 첫 행의 맨 끝으로 설정한다.

2. 첫 행의 맨 끝에서 왼쪽으로 이동하면서...
> 만약 matrix[row][col] > target이라면/col을 1감소시킨다(왼쪽으로 이동해서 값을 작게)
> 만약 matrix[row][col] < target이라면/row를 1증가시킨다(아래쪽으로 이동해서 더 값을 크게)
> 만약 matrix[row][col] == target이라면/바로 return True를 해서 프로그램을 종료시킨다.

3. row, col이 탐색 범위를 벗어났는데도 target을 찾지 못하면 return False 한다.

💡 새롭게 알게 된 점

-