cgy12306
[백준 BoJ] 2636 - 치즈 본문
// https://www.acmicpc.net/problem/2636
// 치즈
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
int N, M, cnt = 0, time = 0;
int map[102][102];
int visited[102][102];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
queue<pair<int, int>> q;
vector<int> cv;
void bfs() {
while (cnt) {
memset(visited, 0, sizeof(visited));
visited[0][0] = true;
q.push({ 0,0 });
cv.push_back(cnt);
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (map[nx][ny] == 0 && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({ nx,ny });
}
else if (map[nx][ny] == 1 && !visited[nx][ny]) {
visited[nx][ny] = true;
map[nx][ny] = 0;
cnt--;
}
}
}
time++;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
if (map[i][j] == 1) cnt++;
}
}
bfs();
cout << time << "\n" << cv[cv.size()-1];
}
- BFS
'Algorithm > C++' 카테고리의 다른 글
[백준 BoJ] 3055 - 탈출 (0) | 2022.03.18 |
---|---|
[백준 BoJ] 2206 - 벽 부수고 이동하기 (0) | 2022.03.18 |
[백준 BoJ] 24678 - 돌무더기 게임 1 (0) | 2022.03.13 |
[백준 BoJ] 1113 - 수영장 만들기 (0) | 2022.03.08 |
[백준 BoJ] 12582 - 1로 만들기 2 (0) | 2022.03.08 |
Comments