Leetcode 1970. Last Day Where You Can Still Cross

https://leetcode.com/problems/last-day-where-you-can-still-cross/description/

Last Day Where You Can Still Cross - LeetCode

문제

인덱스 1부터 시작하는 2차원 배열은 땅을 뜻하는 0과 물을 뜻하는 배열이며 함께 주어지는 열의 갯수의 정보를 담고있는 col과 행의 갯수를 담고있는 row가 주어진다.

 

첫번째 날에는 2차원 배열 모든 원소가 땅으로 이루어져있다. 하지만 날이 지나갈수록 물이 범람하며 물이 범람하는 장소는 cells 파라미터에 정보가 담겨있다. cells[i] = [r, c]으로 이루어진 cells 배열은 i번째 날에 i번째 행인 r, i번째 열인 c에서 물이 범람함을 의미한다.

 

이 정보를 바탕으로 배열의 위에서 아래로 걸어갈 수 있는 마지막 요일을 찾으면 된다. 땅으로 이루어진 곧은 어디든 갈 수 있으며 물은 건널 수 없다. 또한 방향은 상 하 좌 우 4가지 방향으로만 움직일 수 있다.

 

코드

from collections import deque

class Solution:

    def latestDayToCross(self, row: int, col: int, cells: list[list[int]]) -> int:

        cardi = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def isThrough(cells, m) -> bool:

            matrix = [[0 for i in range(col)] for _ in range(row)]

            for i in range(m+1):

                matrix[cells[i][0]-1][cells[i][1]-1]=1

            visited = set()

            for i in range(col):

                if matrix[0][i] != 1:

                    que = deque([[0, i]])

                    # visited = [(0, i)]

                    while que:

                        r, c = que.popleft()

                        if r == row - 1:

                            return True

                        for d in cardi:

                            rr = r + d[0]

                            cc = c + d[1]

                            if 0 <= rr < row and 0 <= cc < col and (rr, cc) not in visited and matrix[rr][cc] != 1:

                                que.append([rr, cc])

                                visited.add((rr, cc))

            return False

       

        answer = 0

        l = 0

        r = len(cells) - 1

        while l <= r:

            m = (l + r) >> 1

            # print(f"{l} ~ {r} at {m}")

            if isThrough(cells, m):

                l = m + 1

                answer = m + 1

            else:

                r = m - 1

        return answer

---

 

BFS + 바이너리 서치를 이용한 해답. 중간에 시간초과가 생겨서 어떻게 할까 생각하다가 cell이 추가된 이후 단계에서 visited를 초기화 할 필요가 없음을 깨닫고 visited를 중복해서 사용하여 중간에 연산을 끊어 시간초과를 해결할 수 있었음.