[알고리즘] 코테 유형 분석 6-1. BFS 사용 팁

안녕하세요 오늘은 bfs를 사용할 때 주의해야 할 점에 대해서 말씀드리겠습니다.

결론부터 말씀드리자면 bfs는 체크를 한 이후에 큐에 넣는 것이 더 좋다입니다. DFS의 경우 재귀 함수 호출 시 체크해도 체크 이전과 체크 이후 간의 간극이 짧습니다. 하지만 BFS의 경우 체크를 큐에서 꺼낼 때 진행하게 될 경우 해당 데이터의 값은 큐에서 꺼내질때 동안 체크 처리가 되어 있지 않은 상태가 됩니다. 즉 이 데이터가 큐에서 꺼내지기 전 다른 데이터가 해당 데이터 값을 지나게 될 경우 중복해서 탐색하는 문제가 발생하여 시간 초과 및 메모리 초과가 발생 가능합니다.

아래는 백준 7562(나이트의 이동) 문제 풀이 중 일부입니다. 아래는 큐에서 값을 꺼내올 때 체크를 처리하고 있으며 새로운 위치가 체크되지 않았을 경우 바로 체크하지 않고 큐에서 꺼내질 때까지 대기합니다. 따라서 사이에 다른 연산으로 인해 같은 위치값에 접근하게 될 경우 중복해서 탐색하게 됩니다. 따라서 이렇게 진행하면 메모리 초과가 발생합니다.

        while(!queue.isEmpty()){
            Knight curr = queue.poll();
            check[curr.y][curr.x] = true;

            if(curr.y == fy && curr.x == fx) return curr.cnt;
            for(int i=0;i<8;i++){
                int ny = curr.y + dy[i];
                int nx = curr.x + dx[i];
                if(ny<0 || ny>=N || nx<0 || nx>=N) continue;

                if(!check[ny][nx]){
                    queue.add(new Knight(ny,nx,curr.cnt+1));
                }
            }
        }

아래는 새로운 위치를 바로 체크하는 방식입니다. 최초값은 while 바깥에서 미리 체크를 진행하며 새롭게 탐색한 곳이 조건에 부합할 경우 바로 체크를 진행합니다. 이를 통해 중복 참조를 방지하여 시간 및 메모리를 절약할 수 있습니다.

        while(!queue.isEmpty()){
            Knight curr = queue.poll();

            if(curr.y == fy && curr.x == fx) return curr.cnt;
            for(int i=0;i<8;i++){
                int ny = curr.y + dy[i];
                int nx = curr.x + dx[i];
                if(ny<0 || ny>=N || nx<0 || nx>=N) continue;

                if(!check[ny][nx]){
                    check[ny][nx] = true;
                    queue.add(new Knight(ny,nx,curr.cnt+1));
                }
            }
        }