[Softeer/소프티어][level3] 동계 테스트 시점 예측 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=411

Softeer

 

 

[난이도] level3
[유형] DFS

[풀이]
가장자리에는 얼음이 없다는 것이 보장되기 때문에
0,0에서부터 0(얼음) 인 점을 탐색하면서 4방향을 검사해서 얼음이 있으면 얼음의 좌표에 외부 공기에 접한 횟수를 카운팅 해줍니다.
그 뒤 2이상 카운팅된 얼음을 지워주는 것을 모든 얼음이 사라질때까지 반복하면 됩니다.

 

#include <cstdio>
#include <cstring>
int N,M,dy[4]={-1,1,0,0},dx[4]={0,0,1,-1};
int map[100][100],cnt[100][100],visit[100][100],ans;
void dfs(int y,int x){
    visit[y][x]=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||visit[ny][nx]) continue;
        if(map[ny][nx]){
            cnt[ny][nx]++;
        }else{
            dfs(ny,nx);
        }
    }
}
bool exist(){
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) if(map[i][j]) return true;
    return false;
}
int main(){
    bool ok=0;
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++) {
            scanf("%d",&map[i][j]);
            if(map[i][j]) ok=1;
        }
    while(ok){
        ans++;
        dfs(0,0);
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++) if(cnt[i][j]>=2) map[i][j]=0;
        ok=exist();
        memset(visit,0,sizeof(visit));
        memset(cnt,0,sizeof(cnt));
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/동계_테스트_시점_예측.cpp