코드
#include <bits/stdc++.h>
using namespace std;
int n,m,res,timecnt;
int graph[104][104];
int visited[104][104];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
vector<pair<int,int>> cheeze;
void dfs(int x, int y) {
visited[x][y] = 1;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= n || ny >= m || nx < 0 || ny < 0) continue;
if(graph[nx][ny] == 1&&!visited[nx][ny]) {
visited[nx][ny] = 1;
cheeze.push_back({nx, ny});
}
if(graph[nx][ny] == 0&&!visited[nx][ny]) {
dfs(nx, ny);
}
}
}
int main() {
cin >> n >> m;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
while(1) {
timecnt++;
dfs(0,0);
int temp = cheeze.size();
for(int i = 0; i < cheeze.size(); i++) {
graph[cheeze[i].first][cheeze[i].second] = 0;
}
if (temp == 0) break;
res = temp;
memset(visited,0,sizeof(visited));
cheeze.clear();
}
cout << timecnt-1 << '\n' << res << '\n';
return 0;
}
풀이
구멍에서는 치즈가 녹지 않으므로 바깥쪽에서 처음 만나는 친구들만 체크했다가 녹이면 된다. 가장자리에는 치즈가 없으므로, 0,0에서 출발하면 편하게 해결할 수 있다.
'백준' 카테고리의 다른 글
[백준] 1189번 컴백홈 C++ 코드 (0) | 2024.04.22 |
---|---|
[백준] 12851번 숨바꼭질 2 C++ 코드 (0) | 2024.04.21 |
[백준] 14502번 연구소 C++ 코드 (0) | 2024.04.18 |
[백준] 4659번 비밀번호 발음하기 C++ 코드 (0) | 2024.04.11 |
[백준] 1676번 팩토리얼 0의 개수 C++ 코드 (0) | 2024.04.11 |