Leetcode - 240. Search a 2D Matrix II

문제

풀이

고전적인 BFS 완전탐색 풀이

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def is_safe(x, y):
            if (
                -1 < x < len(matrix)
                and -1 < y < len(matrix[0])
                and visited[x][y] != 1
            ):
                return True
            return False

        moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        visited[0][0] = 1
        queue = [(0, 0)]
        while queue:
            x, y = queue.pop()

            if matrix[x][y] == target:
                return True

            for dx, dy in moves:
                x_ = x + dx
                y_ = y + dy
                if is_safe(x_, y_):
                    queue.append((x_, y_))
                    visited[x_][y_] = 1

        return False

두 방향으로만 이동

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = len(matrix) - 1
        col = 0
        while row >= 0 and col < len(matrix[0]):
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                col += 1
            else:
                row -= 1
        return False