2638

어떻게 외부 공기를 깔끔하게 처리할 것이냐가 위 문제를 푸는데 가장 중요한 요소이다

초등부 문제와는 다르게 위 문제는 격자 가장자리에도 치즈를 올려 둘 수 있다는 조건이 문제를 푸는데 어려운 요소였던 것 같다.

그래서 나는 애초에 치즈 격자를 1,1 부터 시작하게 한 후

바깥 공기를 찾기 위해서 0,0 부터 찾도록 만들었다.

즉 문제에서 주어진 격자 보다 2열을 더 추가해 격자를 만들고 추가한 격자를 이용해

바깥 공기를 자동으로 찾을 수 있도록 만들었다.

#include<iostream> #include<cstdio> #include<queue> #include<fstream> using namespace std; int map[105][105]; int main(){ int R, C; int res=0; queue<pair<int, int> > q; int clk=0; ifstream ifp("input.txt"); ifp>>R>>C; //scanf("%d %d", &R, &C); for(int i=1; i<=R; i++){ for(int j=1; j<=C; j++){ ifp>>map[i][j]; //scanf("%d", &map[i][j]); } } while(1){ q.push(make_pair(0,0)); map[0][0]=3; while(!q.empty()){ pair<int, int> front = q.front(); q.pop(); int x = front.first; int y = front.second; if(x+1<=R+1) { if(map[x+1][y]==0){ map[x+1][y]=3; q.push(make_pair(x+1, y)); } } if(x-1>=0) { if(map[x-1][y]==0){ map[x-1][y]=3; q.push(make_pair(x-1, y)); } } if(y+1<=C+1) { if(map[x][y+1]==0){ map[x][y+1]=3; q.push(make_pair(x, y+1)); } } if(y-1>=0) { if(map[x][y-1]==0){ map[x][y-1]=3; q.push(make_pair(x, y-1)); } } } res=0; for(int i=0; i<=R+1; i++){ for(int j=0; j<=C+1; j++){ if(map[i][j]==1){ int count=0; if(i-1>=0&&map[i-1][j]==3) count++; if(i+1<R&&map[i+1][j]==3) count++; if(j-1>=0&&map[i][j-1]==3) count++; if(j+1<C&&map[i][j+1]==3) count++; if(count>=2) { res++; map[i][j]=2; } } } } for(int i=0; i<=R+1; i++) for(int j=0; j<=C+1; j++){ if(map[i][j]==3||map[i][j]==2) map[i][j]=0; } if(res==0){ printf("%d\n", clk); return 0; } clk++; } return 0; }