BFS 메모리 줄이는 방법

BFS에서 visit 배열을 거리 저장 용도로 사용하고는 한다.

 

int vis[N][M]={}, dr[] = {1,0,-1,0}, dc[] = {0,1,0,-1};
queue<pair<int,int>> q;

q.push({sr,sc});
vis[sr][sc] = 1;

while(!q.empty()){
	auto t = q.front(); q.pop();
   	int r = t.first, c = t.second;
    for(int i=0;i<4;i++){
    	int nr = r + dr[i], nc = c + dc[i];
        if(safe(nr,nc) && !vis[nr][nc]){
        	vis[nr][nc] = vis[r][c] + 1;
            q.push({nr,nc});
        }
    }
}

return vis[er][ec] - 1;

위는 이차원 격자판에서 BFS를 시행하는 전형적인 코드이다.

이 경우 큐에 거리 정보가 들어갈 필요가 없다는 것이 장점이다.

하지만 보통 최종적으로 구하는 것은 (sr,sc)에서 (er,ec)까지의 거리다. 고로 다른 격자점까지의 거리는 '갱신'의 과정 외에는 그렇게 쓸모가 없다. 여기서 모든 거리를 저장하는 것은 낭비라고 생각된다.

 

vis 배열을 기존의 목적대로 '체크'만 할거라면 bool형으로 잡으면 된다.

그럼 거리는 어떻게 저장할까?

우리는 큐에는 오직 연속적인 거리를 가진 노드만 들어간다는 사실을 이용할 것이다.

 

큐에 거리 정보를 넣는다고 생각하면 

 

0(시작점) 1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 3 3 ..... X X X(도착점)

 

이런 순서로 들어간다.

큐는 선입 선출이므로 저 순서대로 살펴볼 것이고, 고로 거리 변수 하나를 들고 다니면서 도착점에 도착했을 경우 이를 출력하면 된다.

 

다음은 위를 구현한 코드다.

 

bool vis[N][M]={};
int dr[] = {1,0,-1,0}, dc[] = {0,1,0,-1};
queue<pair<int,int>> q;

q.push({sr,sc});
vis[sr][sc] = 1;
int dist = 0;

while(!q.empty()){
   for(int sz = q.size(); sz>0 ; sz--){
    	auto t = q.front(); q.pop();
        int r = t.first, c = t.second;
      
        if(r==er && c==ec)
          return dist;

        for(int i=0;i<4;i++){
            int nr = r + dr[i], nc = c + dc[i];
            if(safe(nr,nc) && !vis[nr][nc]){
                vis[nr][nc] = 1;
                q.push({nr,nc});
            }
        }
    }
    ++dist;
}

return -1;

 

 

Q에 현재 있는 원소들이 현재 dist 값을 가진 노드들이기 때문에

for(int sz = q.size(); sz>0; sz--)

이 for문이 dist 값을 가진 노드들만이 큐에서 빠지게 해준다.