


백준 2638 치즈
백준 2638 치즈
2022년 12월 4일
2022년 12월 4일
cpp, 탐색
문제
문제
풀이
풀이
이전 치즈 문제와 마찬가지로 공기와 접촉하는 면을 찾은 후 지워주는 과정을 반복한다.
이때 공기와 접촉하는 면은 치즈가 놓이지 않는 가장자리부터 탐색을 시작할 때, 해당 영역에 인접한 면이다.
코드
코드
#include <bits/stdc++.h>
using namespace std;
int n,m;
int cheese[102][102];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
bool find_cheese(){
bool is_remain = false;
bool vis[102][102] = {0,};
bool oneTouch[102][102] = {0,};
queue<pair<int,int>> q;
vis[0][0] = true;
q.push({0,0});
while(!q.empty()){
auto [x,y] = q.front(); q.pop();
for(int dir=0; dir<4; ++dir){
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx<0||ny<0||nx>=n||ny>=m) continue;
if(vis[nx][ny]) continue;
if(cheese[nx][ny] == 1){
is_remain = true;
if(oneTouch[nx][ny]){
// 치즈를 지우는 과정이 다른 치즈를 찾는 과정에 영향을 미치지 않으므로 한번에 진행한다.
cheese[nx][ny] = 0;
vis[nx][ny] = true;
continue;
}
oneTouch[nx][ny] = true;
continue;
}
vis[nx][ny] = true;
q.push({nx,ny});
}
}
return is_remain;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0; i<n; ++i)
for(int j=0; j<m; ++j)
cin >> cheese[i][j];
int cnt = 0;
while(find_cheese()) cnt++;
cout << cnt;
}
결과
결과

Copyright © 2024 Hyunghoon Kim