[leetCode/JS] 1970. Last Day Where You Can Still Cross

난이도 [ 👿 ] Hard

 

문제 설명 

There is a 1-based binary matrix where 0 represents land and 1 represents water. You are given integers row and col representing the number of rows and columns in the matrix, respectively.

 

Initially on day 0, the entire matrix is land. However, each day a new cell becomes flooded with water. You are given a 1-based 2D array cells, where cells[i] = [ri, ci] represents that on the ith day, the cell on the rith row and cith column (1-based coordinates) will be covered with water (i.e., changed to 1).

 

You want to find the last day that it is possible to walk from the top to the bottom by only walking on land cells. You can start from any cell in the top row and end at any cell in the bottom row. You can only travel in the four cardinal directions (left, right, up, and down).

 

Return the last day where it is possible to walk from the top to the bottom by only walking on land cells.

 

🌊 마지막으로 건널 수 있는 날 찾기 (Last Day to Walk Across)

0은 땅을 나타내고 1은 물을 나타내는 '1-기반(1-based)' 이진 행렬이 있습니다. 행렬의 행과 열의 개수를 나타내는 정수 row와 col이 주어집니다.
처음 0일차에는 행렬의 전체가 땅입니다. 하지만 매일 새로운 칸 하나가 물에 잠기게 됩니다. 당신에게는 '1-기반' 2차원 배열 cells가 주어지며, 여기서 cells[i] = [ri, ci]는 $i$번째 날에 $r_i$행 $c_i$열(1-기반 좌표)에 있는 칸이 물로 덮임(즉, 1로 변경됨)을 의미합니다.
당신은 오직 땅(0)으로만 이동하여 맨 윗줄(top)에서 맨 아랫줄(bottom)까지 걸어갈 수 있는 마지막 날이 언제인지 찾고 싶습니다. 맨 윗줄의 어느 칸에서든 시작할 수 있으며, 맨 아랫줄의 어느 칸에서든 끝낼 수 있습니다. 이동은 오직 상, 하, 좌, 우 네 방향으로만 가능합니다.
땅으로만 걸어서 맨 윗줄에서 맨 아랫줄까지 횡단할 수 있는 마지막 날을 반환하세요.

 

입출력 예

Example 1:

Input: row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]] 
Output: 2
Explanation: The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.

 

 

 

Example 2:

Input: row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]] 
Output: 1 
Explanation: The above image depicts how the matrix changes each day starting from day 0. 
The last day where it is possible to cross from top to bottom is on day 1.

 

 

Example 3:

Input: row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]] 
Output: 3 
Explanation: The above image depicts how the matrix changes each day starting from day 0. 
The last day where it is possible to cross from top to bottom is on day 3.

 

 

Constraints

• 2 <= row, col <= 2 * 104 
• 4 <= row * col <= 2 * 104 
• cells.length == row * col 
• 1 <= ri <= row 
• 1 <= ci <= col 
• All the values of cells are unique.

 

 

 

---

내 솔루션

/**
 * https://leetcode.com/problems/last-day-where-you-can-still-cross
 * @param {number} row - 전체 행의 수
 * @param {number} col - 전체 열의 수
 * @param {number[][]} cells - 매일 물에 잠기는 좌표 리스트 (1-based)
 * @return {number} - 건널 수 있는 마지막 날짜
 */
var latestDayToCross = function (row, col, cells) {
    let answerDay = 0;
    // 이진 탐색을 위한 범위 설정 (0일부터 마지막 날까지)
    let left = 0;
    let right = cells.length - 1;

    /**
     * 특정 날짜(day)에 위에서 아래로 건널 수 있는지 확인하는 함수 (BFS)
     */
    const canCross = (day) => {
        // 1. 해당 날짜의 격자 상태 생성 (0: 땅, 1: 물)
        const grid = Array.from({ length: row }, () => new Array(col).fill(0));
        
        // 2. 0일부터 day일까지의 cells를 바탕으로 격자에 물 채우기
        // i < day 이므로, day가 3이면 cells[0], [1], [2] (3일치)를 채움
        for (let i = 0; i < day; i++) {
            const [r, c] = cells[i];
            grid[r - 1][c - 1] = 1; // 1-based 좌표를 0-based 인덱스로 변환
        }

        // 3. BFS 탐색 준비
        const queue = [];
        const visited = Array.from({ length: row }, () => new Array(col).fill(false));
        
        // 4. 시작 지점 설정: 맨 윗줄(row 0)에서 땅(0)인 곳을 모두 큐에 삽입
        for (let i = 0; i < col; i++) {
            if (grid[0][i] === 0) {
                queue.push([0, i]);
                visited[0][i] = true; // 중복 방문 방지
            }
        }

        // 5. 탐색 시작 (상하좌우 방향 설정)
        const direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]; 
        
        while (queue.length > 0) {
            const [curR, curC] = queue.shift();
            
            // 목적지 도착: 맨 아랫줄(row - 1)에 도달하면 건너기 성공
            if (curR === row - 1) return true; 

            for (const [dirR, dirC] of direction) {
                const nextR = curR + dirR;
                const nextC = curC + dirC;
                
                // 격자 범위 내에 있고, 물이 아니며(0), 아직 방문하지 않은 경우만 이동
                if (nextR >= 0 && nextC >= 0 && nextR < row && nextC < col &&
                    grid[nextR][nextC] === 0 && !visited[nextR][nextC]) {
                    
                    visited[nextR][nextC] = true; // 방문 표시 (중요: nextR, nextC 사용)
                    queue.push([nextR, nextC]); // 다음 탐색 후보로 큐에 추가
                }
            }
        }

        // 모든 경로를 탐색했으나 아랫줄에 도달하지 못한 경우
        return false;
    }

    /**
     * 이진 탐색(Binary Search) 수행
     * 매일 BFS를 돌리면 느리기 때문에, '건널 수 있는 날'의 경계선을 Up/Down 게임처럼 탐색
     */
    while (left <= right) {
        // 중간 날짜(mid)를 선택
        const mid = Math.floor((left + right) / 2);
        
        if (canCross(mid)) {
            // 해당 날짜에 건널 수 있다면, 더 늦은 날짜가 가능한지 확인
            answerDay = mid; // 현재 날짜를 정답 후보로 저장
            left = mid + 1;  // 범위를 뒤쪽(더 큰 날짜)으로 좁힘
        } else {
            // 해당 날짜에 건널 수 없다면, 너무 많이 잠긴 것이므로 더 앞선 날짜 확인
            right = mid - 1; // 범위를 앞쪽(더 작은 날짜)으로 좁힘
        }
    }
    
    return answerDay;
};

 

감상평

• 처음엔 day 1 -> day end 까지 순회하려고 했는데, 너무 오래 걸릴 것 같아서 바이너리 서치로 변경
• BFS + 바이너리 서치 2가지 조합이 필요한 문제. 역시 Hard는 달라
• 최적화는 못하겠다. 너무 힘듦.. 이거 1시간 짜리 코테에서 나오면 바로 맨붕인데 ㅋㅋㅋ
• 최소 4시간 급 코테에서 1문제 정도 등장할 가능성이 있어보임..