1970. Last Day Where You Can Still Cross

문제 링크

Last Day Where You Can Still Cross - LeetCode

1. 접근 방식: 이분 탐색 (Binary Search)과 BFS

이 문제의 핵심은 "특정 날짜($D$)에 건널 수 있다면, 그 이전 날짜($D-1, D-2, \dots$)에도 반드시 건널 수 있다"는 결정론적 성질을 이용하는 것입니다.

단순히 1일부터 차례대로 확인하면 시간 초과(TLE)가 발생할 수 있지만, 이분 탐색을 적용하면 탐색 범위를 획기적으로 줄일 수 있습니다.

• 이분 탐색 범위: 0일(시작)부터 cells.length일(전체)까지.
  
• 판별 함수 (BFS): 특정 날짜(Day)를 기준으로 격자를 구성한 뒤, 첫 번째 행(Row 0)에서 마지막 행(Row N-1)까지 도달 가능한 경로가 있는지 탐색합니다.
  

2. 알고리즘 설계

1. Binary Search: 가능한 날짜의 범위를 절반씩 줄여나가며 최적의 '마지막 날'을 찾습니다.

2. BFS 탐색:

   • 해당 날짜까지 침수된 셀들을 격자에 표시합니다.
     
   • 첫 번째 행의 모든 열 중 침수되지 않은 곳을 시작점으로 큐(Queue)에 삽입합니다.
     
   • 상하좌우로 이동하며 마지막 행에 도달하면 true, 도달하지 못하면 false를 반환합니다.
     

3. 유의 사항 및 복잡도 분석

• 좌표 변환: 문제에서 주어지는 좌표는 1-based index이므로, 배열 인덱스로 사용할 때 -1 처리를 해주어야 합니다.
  
• 탐색 종료 조건: 첫 번째 행에서 시작해 어느 열이든 관계없이 마지막 행에 닿기만 하면 탈출 가능으로 간주합니다.
  
• 시간 복잡도: $O(R \times C \times \log(R \times C))$
  • 이분 탐색 범위: $\log(R \times C)$
    
  • 각 탐색마다 BFS 수행: $O(R \times C)$
    

4. Correct Code (Java)

class Solution {
    private int[][] cells;
    private int row, col;
    private final int[] dy = {-1, 1, 0, 0};
    private final int[] dx = {0, 0, -1, 1};

    public int latestDayToCross(int row, int col, int[][] cells) {
        this.cells = cells;
        this.row = row;
        this.col = col;

        int left = 0, right = cells.length - 1;
        int lastPossibleDay = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canCross(mid)) {
                lastPossibleDay = mid + 1; // 0-based index 보정
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return lastPossibleDay;
    }

    private boolean canCross(int day) {
        boolean[][] grid = new boolean[row][col];
        // 해당 날짜까지 침수된 지역 표시
        for (int i = 0; i <= day; i++) {
            grid[cells[i][0] - 1][cells[i][1] - 1] = true;
        }

        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[row][col];

        // 첫 번째 행에서 시작 가능한 모든 지점 큐에 삽입
        for (int j = 0; j < col; j++) {
            if (!grid[0][j]) {
                queue.add(new int[]{0, j});
                visited[0][j] = true;
            }
        }

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int r = curr[0];
            int c = curr[1];

            if (r == row - 1) return true; // 마지막 행 도달 성공

            for (int i = 0; i < 4; i++) {
                int nr = r + dy[i];
                int nc = c + dx[i];

                if (isOutOfRange(nr, nc) || visited[nr][nc] || grid[nr][nc]) continue;

                visited[nr][nc] = true;
                queue.add(new int[]{nr, nc});
            }
        }
        return false;
    }

    private boolean isOutOfRange(int r, int c) {
        return r < 0 || r >= row || c < 0 || c >= col;
    }
}

5. 마치며

이 문제는 "최댓값/최솟값을 찾는 문제"를 "가능 여부를 묻는 결정 문제"로 변환하여 이분 탐색으로 푸는 전형적인 파라메트릭 서치(Parametric Search) 유형입니다. BFS와 이분 탐색의 조합이 익숙하다면 충분히 풀어낼 수 있는 문제였습니다.