https://www.acmicpc.net/problem/2636
2636번: 치즈
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓
www.acmicpc.net
[난이도] Gold5
[유형] DFS
[풀이]
DFS
#include <cstdio> #include <cstring> int N,M,a[102][102],b[102][102],tmp[102][102]; int dy[4]={-1,1,0,0},dx[4]={0,0,1,-1}; void dfs(int y,int x){ b[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||a[ny][nx]||b[ny][nx]) continue; dfs(ny,nx); } } int dfs2(int y,int x){ b[y][x]=1; int ret=1; for(int i=0;i<4;i++){ int ny=y+dy[i],nx=x+dx[i]; if(a[ny][nx] && !b[ny][nx]) ret+=dfs2(ny,nx); } return ret; } int cnt(){ memset(b,0,sizeof(b)); int ret=0; for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(a[i][j] && !b[i][j]) ret+=dfs2(i,j); return ret; } void rmv(){ memset(b,0,sizeof(b)); memset(tmp,0,sizeof(tmp)); dfs(0,0); for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ bool ok=0; for(int k=0;k<4;k++){ int ny=i+dy[k],nx=j+dx[k]; if(b[ny][nx]){ ok=1; break; } } tmp[i][j]=ok; } } for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) if(tmp[i][j]) a[i][j]=0; } int main(){ scanf("%d%d",&N,&M); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) scanf("%d",&a[i][j]); int prev=cnt(); for(int t=0;;t++){ int cur=cnt(); if(cur==0) { printf("%d\n%d",t,prev); return 0; } rmv(); prev=cur; } }
https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2636.cpp
'Problem-Solving > BOJ' 카테고리의 다른 글
[BOJ/백준][Gold5] 14226 : 이모티콘 (C++) (0) | 2021.03.25 |
---|---|
[BOJ/백준][Gold5] 12851 : 숨바꼭질 2 (C++) (0) | 2021.03.25 |
[BOJ/백준][Gold5] 13549 : 숨바꼭질 3 (C++) (0) | 2021.03.25 |
[BOJ/백준][Gold5] 17070 : 파이프 옮기기 1 (C++) (0) | 2021.03.25 |
[BOJ/백준][Gold4] 1963 : 소수 경로 (C++) (0) | 2021.03.25 |