(25.01.15) BFS 알고리즘의 메모리 부족 Memory Limit 해결

BFS 알고리즘을 활용하면서 bigint 내지는 BigIntegerdml 10^19 정도 크기 그 이상의 과학적 계산의 영역의 큰 규모의 데이터를 다룰 떄는 전체 탐색이라는 알고리즘의 특성상 리소스가 초과적으로 발생할 수 있다.

 

이 때는 주어진 Resource를 최대한 활용하면서 두개의 BFS를 활용하면서 제한된 리소스에서 BFS를 통해 이상적인 답을 찾아나가는 알고리즘에 대해서 좀 더 찾아보고 공부하면서 기록을 했다.

---

 

Question

There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are (x, y).

We start at the source = [sx, sy] square and want to reach the target = [tx, ty] square. There is also an array of blocked squares, where each blocked[i] = [xi, yi] represents a blocked square with coordinates (xi, yi).

Each move, we can walk one square north, east, south, or west if the square is not in the array of blocked squares. We are also not allowed to walk outside of the grid.

Return true if and only if it is possible to reach the target square from the source square through a sequence of valid moves.

import java.util.*;

class Solution {
    // 방향키
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    static final int LIMIT = 1000000; // big num 상수화 1 million
    static final int MAX_CELLS = 20000; // 최대 셀 수 제한

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        // blocked 좌표들을 set으로 변환
        Set<String> blockedSet = new HashSet<>();
        for (int[] coordinate : blocked) {
            blockedSet.add(coordinate[0] + "," + coordinate[1]);
        }

        // 1. source -> target으로의 경로가 가능한지 검사
        if (!bfs(source, target, blockedSet)) return false;

        // 2. target -> source으로의 경로가 가능한지 검사
        if (!bfs(target, source, blockedSet)) return false;

        return true;
    }

    // 경로 탐색 함수
    public boolean bfs(int[] source, int[] target, Set<String> blockedSet) {
        Set<String> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        
        visited.add(source[0] + "," + source[1]);
        queue.add(new int[]{source[0], source[1]});
        
        // 메모리 제한용 카운트
        int count = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int currentX = current[0];
                int currentY = current[1];

                // 목표 좌표에 도달했으면 종료
                if (currentX == target[0] && currentY == target[1]) return true;

                // 상하좌우 탐색
                for (int d = 0; d < 4; d++) {
                    int nextX = currentX + dx[d];
                    int nextY = currentY + dy[d];

                    // 각 좌표가 0 이상 1000000 미만인지, 방문하지 않았고, blocked가 아닌지 확인
                    if (0 <= nextX && nextX < LIMIT && 0 <= nextY && nextY < LIMIT &&
                        !visited.contains(nextX + "," + nextY) && 
                        !blockedSet.contains(nextX + "," + nextY)) {
                        
                        // 방문처리
                        visited.add(nextX + "," + nextY);
                        queue.add(new int[]{nextX, nextY});
                    }
                }
            }

            // 탐색한 갯수를 추가하면서  count
            count += size;
            
            // 최대 탐색 셀을 넘으면 경로가 있다고 판단
            if (count > MAX_CELLS) return true; 
        }

        return false; // 목표에 도달하지 못한 경우
    }
}

문제상황

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

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {

        return bfs(blocked, source, target);
    }

    public boolean bfs(int[][] blocked, int[] source, int[] target) {
        // queue vistied 생성
        Set<String> visited = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        
        // 초기 설정
        visited.add(source[0]+","+source[1]);
        queue.add(new int[]{source[0], source[1]});

        // blocked 모음 set으로 만듬
        Set<String> blockedSet = new HashSet<>();
        for (int[] coordinate : blocked) {
            blockedSet.add(coordinate[0]+","+coordinate[1]);
        }

        //while문
        while(!queue.isEmpty()){
            int size = queue.size();

            for(int i =0; i<size; i++) {
                int[] current = queue.poll();
                int currentX = current[0];
                int currentY = current[1];

                // 도달했는지 확인
                if(currentX == target[0] && currentY == target[1]) return true;

                // 상하좌우로 움직이면서 확인
                for(int d = 0; d < 4; d++) {
                    int nextX = currentX + dx[d];
                    int nextY = currentY + dy[d];
                    
                    // 각 좌표점은 0 이상 1000000미만
                    // 미방문
                    if(0 <= nextX && nextX < 1000000 &&
                    0 <= nextY && nextY < 1000000 &&
                    !visited.contains(nextX+","+nextY) &&
                    !blockedSet.contains(nextX+","+nextY)) {
                        visited.add(nextX+","+nextY);
                        queue.add(new int[]{nextX, nextY});
                    }
                }
            }
        }

        return false;
    } 
}

• 위의 초기 알고리즘 코드상황에서 Time Limit Exceeded 가 발생
  • visited 와 queue의 자료구조의 탐색 시간복잡도를 더 줄이기 위해 Array 구조를 Set구조 바꿨음에도 발생
• 테스트로 1 million XY plain 크기가 작아질 경우 일시적으로 Time Limit 이 발생하지 않는 것을 확인

문제 원인

• 1 million x 1 million 의 모든 좌표를 전부 BFS알고리즘을 진행하고자 한다면, 모든 셀을 다 점검해야하는 문제 → 1,000,000,000,000 개의 Plain 위의 좌표들을 탐색하는 총 탐색 시간이 급격히 증가
  • 따라서 Queue 에 등록되는 좌표가 갑자기 늘어나면서 메모리르 많이 사용하게 됨
• BFS 에서 활용해야하는 Queue 자료구조 외 visited 자료구조의 양도 방대하게 증가 → 상하좌우로 좌표를 이동했을 때 해당좌표가 visited 자료구조에서 탐색하면서 찾는 시간도 급격하게 증가

해결 방안 : 이중 BFS 구조를 채택

• 모든 좌표를 다 탐색해야하는 모든 알고리즘의 변형, FLOW 의 시도는 무조건 적으로 Time Limit Exceeded 가 발생
  • 알고리즘 자체의 접근을 달리 해야 → 이중 BFS 구조 활용
  • BFS 자체 알고리즘의 비효율성이 대두
• 탐색하는 최대 좌표갯수 : MAX_CELL을 지정

int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    static final int LIMIT = 1000000; // big num 상수화 1 million
    static final int MAX_CELLS = 20000; // 최대 셀 수 제한

    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        // blocked 좌표들을 set으로 변환
        Set<String> blockedSet = new HashSet<>();
        for (int[] coordinate : blocked) {
            blockedSet.add(coordinate[0] + "," + coordinate[1]);
        }

        // 1. source -> target으로의 경로가 가능한지 검사
        if (!bfs(source, target, blockedSet)) return false;

        // 2. target -> source으로의 경로가 가능한지 검사
        if (!bfs(target, source, blockedSet)) return false;

        return true;
    }

1. 최대 좌표개수에 도달 할때까지 시작 좌표에서 진행하고, 거꾸로 타겟 좌표에서 시작좌표까지 최대 탐색 좌표 개수만큼 탐색
2. 두개가 정상적으로 막히지 않고(blocked) 없이 진행을 했을 때, 정상적으로 BFS가 작동했다고 가정
3. True 반환, 단 두개의 BFS 와중 하나만 False 여도 False 반환

      			// 탐색한 갯수를 추가하면서  count
            count += size;
            
            // 최대 탐색 셀을 넘으면 경로가 있다고 판단
            if (count > MAX_CELLS) return true; 

1. BFS 의 Queue에서 Level별로 사이즈를 추가 하고(탐색한 좌표의 수) 이 카운트가 최대 탐색 수에 도달하게 된다면 정상적으로 BFS 가 막히지 않고 진행되고 있다고 판단해 true를 반환

• MAX_CELLS 크기를 지정
  • 이는 계산이 아닌 실험적으로 조절할 필요가 있음
  • 본인도 해당 코드가 BFS를 실행하는데 필요한 리소스(메모리, 최대 시간)에 부합할 만한 크기로 설정을 여러번의 테스트를 통해서 확인을 히야함

결론

• 이중 BFS를 사용하는 경우도 있음
  • 두 지점 사이의 경로가 독립적으로 양방향으로 탐색 가능하고, 그 중간에서 만날 수 있을 때
  • **양방향 경로 탐색이 효율적인 상황(자료가 매우 클 때)**에서, 경로를 빠르게 발견 가능
  • 차폐된 공간이나 장애물이 존재하여, 양쪽에서 탐색을 병행하며 경로를 찾는 것이 유리할 때도 사용 가능
    • 시간이 절반으로 줄어들게됨

---

전체탐색을 하는 방식이지만 사실적으로 처음 start와 끝 target 까지의 전체를 탐색하는 알고리즘이기 때문에 여러개의 BFS를 사용해서 효율적으로 답을 도출할 수 있다.

 

실제 비지니스 로직에서는 제한이 있을 수 있지만, 관련해서 알고 있다면 충분히 활요하는데 도움이 될 만한 중요한 내용이라 이해하는데에도 조금 시간이 걸렸지만 기록을 했다.