[BOJ] 벽 부수고 이동하기 4

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

16946번: 벽 부수고 이동하기 4

이 문제를 풀면서 bfs에 대해서 한번 더 배우게 된 것 같다.

알고리즘

1. 전체 반복문을 돌면서 영역에 포함되지 않은 0을 만난다면 bfs를 돌리며 color값을 입력한다.

2. bfs를 돌면서 방문한 0의 좌표를 저장하고 bfs가 끝났으면 해당 영역의 크기를 저장한 좌표에 저장해준다.

3. 다시 전체 반복문을 돌면서 1을 만날 경우 그 칸과 모두 인접한 0에 저장된 영역의 크기를 더해준다. (단, color의 값이 같은 경우는 넘어가야 한다.)

 

이 문제를 구현할 때 나는 bfs를 아래와 같이 구현하였다.

잘못 구현된 bfs

나는 queue에 들어간 좌표가 pop 할 때 영역을 지정해 주었는데 그렇게 되면 중복으로 push되는 점이 발생하게 된다.

따라서 bfs에서는 push할 때 영역을 지정해 주고 push해주어야 한다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
using namespace std;
int dy[]={0,0,1,-1};
int dx[]={1,-1,0,0};
int Map[1001][1001];
int color[1001][1001]; //영역을 지정해주는 배열
int ans[1001][1001]; //해당 좌표가 포합된 영역의 크기를 저장해 주는 배열
int cnt=1;
int N,M;
void bfs(int j,int i,int c){
    int sum=0;
    queue<pair<int,int> > q;
    queue<pair<int,int> > in;
    q.push(make_pair(j,i));
    color[j][i]=c;
    while(!q.empty()){
        int y=q.front().first,x=q.front().second; q.pop();
        in.push(make_pair(y,x));
        sum++;
        for(int i=0;i<4;i++){
            int ny=y+dy[i],nx=x+dx[i];
            if(0<=ny&&ny<N&&0<=nx&&nx<M&&!Map[ny][nx]&&!color[ny][nx]){
                color[ny][nx]=c;
                q.push(make_pair(ny,nx));
            }
        }
    }
    while(!in.empty()){
        int y=in.front().first,x=in.front().second; in.pop();
        ans[y][x]=sum;
    }
}

int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    cin>>N>>M;
    string s;
    for(int i=0;i<N;i++){
        cin>>s;
        for(int j=0;j<M;j++){
            Map[i][j]=s[j]-'0';
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!Map[i][j]&&!color[i][j]){
                bfs(i,j,cnt++);
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(Map[i][j]){
                map<int,int> m;
                for(int k=0;k<4;k++){
                    int ny=i+dy[k],nx=j+dx[k];
                    if(0<=ny&&ny<N&&0<=nx&&nx<M&&!Map[ny][nx]&&!m[color[ny][nx]]){
                        ans[i][j]+=ans[ny][nx];
                        m[color[ny][nx]]=1;
                    }
                }
                cout<<(ans[i][j]+1)%10;
            }else cout<<0;
        }
        cout<<'\n';
    }
    return 0;
}