(25.01.25) DFS 알고리즘의 시간 부족 Time Limit Exceeded 해결

 

 

DFS를 통한 깊이 전체 탐색을 진행하는 알고리즘일 경우엔, 조건에 부합하는 경로가 나올때까지, DFS를 계속해서 진행하는 로직이 구현될 수 있다.

이런 상황에서 탐색해야하는 구간이 커질 수록 Time Limit 이 발생할 수 있다.

 

이 때 활용할 수 있는 간단한 방법을 정리하고자한다.

---

Question

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.

 

class Solution {
    // 방향키
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0,0,-1,1};

    public int latestDayToCross(int row, int col, int[][] cells) {

        // cell 인덱스 표시로 변경
        for(int i = 0; i< cells.length; i++) {
            cells[i][0]--;
            cells[i][1]--;
        }
    
        int day = 0;
        int low = 0;
        int high = cells.length;

        while( low <= high) {

            int mid  = low + (high - low)/2;

             // mid 까지 물채우기
            int[][] grid = new int[row][col];
            for( int i = 0; i < mid; i++ ) {
                grid[cells[i][0]][cells[i][1]] = 1;
            }

            boolean isConnected = false;
            boolean[][] visited = new boolean[row][col];

            for(int r = 0; r < col; r++) {
                if(grid[0][r] == 0) {
                    int startX = 0;
                    int startY = r;
                    if( dfs(grid, visited, startX, startY) ) {
                        isConnected = true;
                        break;
                    };
                }
            }
                
            // while 문 재설정
            if(isConnected) {
                day = mid;
                low = mid +1;
            } else {
                high = mid -  1;
            }

        }
        
        return day;
    }

        public boolean dfs(int[][] grid, boolean[][] visited, int startX, int startY) {
            int m = grid[0].length;
            int n = grid.length;
        
            // y값이 grid 끝에 도달할경우 true
            if(startX == n - 1) return true;

            // 상하좌우 움직이면서 DFS
            for(int d = 0; d <4; d++) {
                int nextX = startX + dx[d];
                int nextY = startY + dy[d];

                // 0이고, 방문을 안했을 경우
                if(0 <= nextX && nextX < n &&
                0 <= nextY && nextY < m &&                    
                    !visited[nextX][nextY] &&
                grid[nextX][nextY] == 0) {
                
                visited[nextX][nextY] = true;

                if( dfs(grid, visited, nextX, nextY) ) return true;
                }
            }
            
            return false;

        }
}

문제상황

class Solution {
    // 방향키
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0,0,-1,1};

    public int latestDayToCross(int row, int col, int[][] cells) {
        int[][] grid = new int[row][col];

        // cell 인덱스 표시로 변경
        for(int i = 0; i< cells.length; i++) {
            cells[i][0]--;
            cells[i][1]--;
        }
    
        int day = 0;

        for(int i = 0 ; i < cells.length; i++) {
            day++;

            int[] coordinate = cells[i];
            int waterX = coordinate[0];
            int waterY = coordinate[1];

            grid[waterX][waterY] = 1;
            
            boolean isConnected = false;

            for(int r = 0; r < col; r++) {
                if(grid[0][r] == 0) {
                    int startX = 0;
                    int startY = r;

                    boolean[][] visited = new boolean[row][col];

                    if( dfs(grid, visited, startX, startY) ) {
                        isConnected = true;
                        break;
                    };
                }
            }
            

            if(!isConnected) return day-1;
        }
        
        return day-1;
    }

        public boolean dfs(int[][] grid, boolean[][] visited, int startX, int startY) {
            int m = grid[0].length;
            int n = grid.length;
        
            // y값이 grid 끝에 도달할경우 true
            if(startX == n - 1) return true;

            // 상하좌우 움직이면서 DFS
            for(int d = 0; d <4; d++) {
                int nextX = startX + dx[d];
                int nextY = startY + dy[d];

                // 0이고, 방문을 안했을 경우
                if(0 <= nextX && nextX < n &&
                0 <= nextY && nextY < m &&                    
                    !visited[nextX][nextY] &&
                grid[nextX][nextY] == 0) {
                
                visited[nextX][nextY] = true;

                if( dfs(grid, visited, nextX, nextY) ) return true;
                }
            }
            
            return false;

        }
}

• 위의 코드를 통해서 grid 크기에 상관 없이 단건 조건에서는 정상적으로 작동되는 알고리즘이지만 주어진 리소스를 통해 여러개의 알고리즘을 실행시키는 환경에선, Time Limit Exceeded 이 발생

문제 원인

• for (int r = 0; r < col; r++) 부분은 첫 번째 행의 모든 열을 시작점으로 DFS를 실행하는 구조로 , 물이 채워질 때 마다 같은 경로를 중복해서 계속 탐색할 수 밖에 없는 구조
  • 물이 생긴다면 기존의 경로가 유효하지 않을 수 있기 때문에 계속적으로 탐색을 진행을 해야함
• 상하좌우를 모두 탐색하면서 복잡한 구조도 탐색해 나가는 구조이기 때문에 복잡한 미로찾기를 매번 계속 반복하는 로직
• BFS 의 메모리 부족처럼 이중 BFS를 사용하는 것 처럼 양 끝에서 접근할 수 없음
  • BFS는 최단 거리 하나를 바로 찾아내는 거지만, DFS는 아무 조건 없이 해당 노드 끝까지 탐색하는 것이기 때문에

해결 방안 : 이분탐색 Binary Search 적용

while( low <= high) {

            int mid  = low + (high - low)/2;
...

					  // while 문 재설정
            if(isConnected) {
                day = mid;
                low = mid +1;
            } else {
                high = mid -  1;
            }
...

return day;

• 탐색 속도를 O(log n)로 최대한 줄일 수 있는 알고리즘을 진행하면서 DFS와 함께 사용
  • 재귀적 DFS를 Binary Serach while문 안에 배치해서 사용하는 방법
• 기존의 O(n) 시간 복잡도 보다 극적으로 (log)로 차이가 발생

Brute Force 타파

• 가능한 모든 경우의 수를 완전 탐색을 통해서 찾아가는 방식
  • DFS를 여러번 진행시키는 알고리즘이 해당할 수 있음
• 비효율적이나 문제의 조건이 제한적이고 경우의 크기가 작을 때 사용할 수 있음
• 단점
  • 경우의 수와 시간복잡도가 급격한 증가 양상을 보일 수 밖에 없음
    • 그리드 전체 탐색, 모든 경우의수 찾기 등 O(n!) O(n^2) 시간복잡도로 안좋은 효율을 보여지게 됨
• HashSet을 사용하거나 부분탐색을 진행하는 등으로 효율적인 방향으로 알고리즘을 작성해야하는 경우도 있음

---

알고리즘이 정상적으로 진행이 되었다고 하더라도 효율성 문제가 항상 발목을 잡아서 코드를 한번씩 점검을 해야하는 경우가 생기는 것 같다.

 

특히  전체탐색을 사용해야하는 상황에서 중복이 반복해서 진행되겠는데 한다면, 바로 Binary Search 와 합친 DFS를 적극적으로 활용해야해야할 것이다.