bfs 방문체크 위치

백준 문제를 풀다 메모리 초과를 만남..

 

분명 다른사람 코드와 같은데, 왜 메모리 초과가 나는지 이상했다.

 

이유는 bfs 방문체크 위치를 잘 못 해서

결론 : 큐에 삽입하는 순간에 방문체킹을 해서 중복을 방지하자

 

잘못된 방문체크 위치 (큐를 뽑는 순간 방문체크)

아래 코드는 문제에 사용된 bfs함수 일부분입니다

static boolean move(){
        Queue<int[]> tmp = new LinkedList<>();

        while(!bq.isEmpty()){

            int[] c = bq.poll();
            int cr = c[0], cc=c[1];
            
            if(cr==er && cc == ec){ 
                return true;
            }

            chk[c[0]][c[1]]=true; // 방문체크

            for(int d=0;d<4;d++){
                int nr = c[0] + dr[d];
                int nc = c[1] + dc[d];

                if(nr<0 || nr>=R) continue;
                if(nc<0 || nc>=C) continue;
                if(chk[nr][nc]) continue;

                if(map[nr][nc]=='.'){
                    bq.add(new int[]{nr,nc});
                }else if (map[nr][nc]=='X'){
                    tmp.add(new int[]{nr,nc});
                }
            }
        }

        bq = tmp; 
        return false;
    }

큐에서 뽑는 순간 방문체크를 수행했다.

 

왜 저렇게 했냐면 시작 좌표의 방문체크를 한 번에 하려고..

 

이렇게 하면, 중복된 좌표가 큐에 들어가게 되어서,, 메모리 초과

 

올바른 방문체크(큐에 넣는 순간 방문체크) 

static boolean move(){
        Queue<int[]> tmp = new LinkedList<>();

        while(!bq.isEmpty()){

            int[] c = bq.poll();
            int cr = c[0], cc=c[1];

            if(cr==er && cc == ec){ 
                return true;
            }

            for(int d=0;d<4;d++){
                int nr = c[0] + dr[d];
                int nc = c[1] + dc[d];

                if(nr<0 || nr>=R) continue;
                if(nc<0 || nc>=C) continue;
                if(chk[nr][nc]) continue;

                chk[nr][nc]=true; // 방문체크

                if(map[nr][nc]=='.'){
                    bq.add(new int[]{nr,nc});
                }else if (map[nr][nc]=='X'){ 
                    tmp.add(new int[]{nr,nc});
                }
            }
        }

        bq = tmp; 
        return false;
    }

큐에 넣는 순간 방문체크를 수행했다.

 

중복 좌표가 큐에 들어가지 않게됨..!

 

이렇게 하려면 bfs 수행부분 밖에서 시작 좌표에 대한 방문체크를 수행해줘야 한다