[ERROR] BFS중 메모리초과

https://www.acmicpc.net/problem/6593

6593번: 상범 빌딩

 

문제를 풀다가 메모리 초과가 발생하였다.

 

메모리초과가 뜨는 이유로 Queue에서 뽑을 때 visited를 처리하는 것이 아닌 Queue에 넣을 때 visited 를 처리해야된다는 것이다.

 

 

[메모리 초과 코드] 

queue.poll() 이후에 visited를 체크한다.

 Queue<int []> queue = new LinkedList<>();
    queue.add(start);

    StringBuilder sb = new StringBuilder();
    int addCount = 0;
    while(!queue.isEmpty()) {
        int [] temp = queue.poll();
        visited[temp[0]][temp[1]][temp[2]] = true;
        for(int i = 0; i < 6; i++) {
            int nX = temp[0] + dx[i];
            int nY = temp[1] + dy[i];
            int nZ = temp[2] + dz[i];

            if(isIn(nX, nY, nZ) && !visited[nX][nY][nZ]) {

                board[nX][nY][nZ] = Math.min(board[temp[0]][temp[1]][temp[2]] + 1, board[nX][nY][nZ]);

                if(nX == end[0] && nY == end[1] && nZ == end[2]) {
                   System.out.println("큐에 들어간 횟수: " + addCount);
                }

                queue.add(new int [] { nX, nY, nZ });
                addCount++;
           }
        }
    }
}

[결과]

큐에 들어간 횟수: 43535

 

 

[통과 코드]

 public void getAnswer(int start[], int end[]) {
    Queue<int []> queue = new LinkedList<>();
    queue.add(start);

    StringBuilder sb = new StringBuilder();
    int addCount = 0;
    while(!queue.isEmpty()) {
        int [] temp = queue.poll();
        for(int i = 0; i < 6; i++) {
            int nX = temp[0] + dx[i];
            int nY = temp[1] + dy[i];
            int nZ = temp[2] + dz[i];

            if(isIn(nX, nY, nZ) && !visited[nX][nY][nZ]) {
                visited[nX][nY][nZ] = true;
                board[nX][nY][nZ] = Math.min(board[temp[0]][temp[1]][temp[2]] + 1, board[nX][nY][nZ]);

                if(nX == end[0] && nY == end[1] && nZ == end[2]) {
                   System.out.println("큐에 들어간 횟수: " + addCount);

                }

                queue.add(new int [] { nX, nY, nZ });
                addCount++;
            }
        }
    }
}

[결과]

큐에 들어간 횟수: 460

43535번에서 460번만 들어간 것을 알 수 있다.

 

조금만 생각해보니 queue에서 뽑을 때 방문처리를 하면 이미 많은 곳에서 해당 인덱스를 거칠수 있기에 넣음과 동시에 방문처리를 함으로서 동일한 곳에 접근을 못하게 할 수 있는 것 같다.

 

[풀이코드]

 

https://github.com/ghrnwjd/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Gold/6593.%E2%80%85%EC%83%81%EB%B2%94%E2%80%85%EB%B9%8C%EB%94%A9/%EC%83%81%EB%B2%94%E2%80%85%EB%B9%8C%EB%94%A9.java