[BOJ/백준][Gold2] 16946 : 벽 부수고 이동하기4 (C++)

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

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

 

 

[난이도] Gold2
[유형] DFS

[풀이]
N,M의 최댓값이 1000이므로 각 점에서 DFS or BFS로 답을 구하면 시간 초과가 난다.
DFS를 전체 맵에 대해 한번씩 돌리면서 빈 칸이 어떤 그룹에 속하는지, 그 그룹의 총 원소의 수는 몇개인지를 기록해놓는다.
그 뒤 맵을 다시 순회하면서 벽이 있는 칸의 4방향을 확인하면서 그룹의 갯수를 더해주면 시간내에 답을 구할 수 있다.

 

#include <cstdio>
#include <set>
using namespace std;
int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int N,M,a[1000][1000],grp[1000][1000],cnt[1000001];
bool visit[1000][1000];
int dfs(int y,int x,int k){
    visit[y][x]=1;
    grp[y][x]=k;

    int ret=1;
    for(int i=0;i<4;i++){
        int ny=y+dy[i], nx=x+dx[i];
        if(ny<0||nx<0||ny>=N||nx>=M||a[ny][nx]||visit[ny][nx]) continue;
        ret+=dfs(ny,nx,k);
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) scanf("%1d",&a[i][j]);
        
    int g=1;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!a[i][j] && !visit[i][j]){
                cnt[g]=dfs(i,j,g);
                g++;
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(!a[i][j]) continue;
            int v=0;
            set<int> p;
            for(int k=0;k<4;k++){
                int ny=i+dy[k],nx=j+dx[k];
                if(ny<0||nx<0||ny>=N||nx>=M||a[ny][nx]) continue;  
                p.insert(grp[ny][nx]);
            }
            for(auto q : p) v+=cnt[q];
            a[i][j]=v+1;
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            printf("%d",a[i][j]%10);
        }
        puts("");
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/16946.cpp