분명히 쉬운 문제인데 생각보다 좀 고전했다. 복잡하게 생각하는 내 버릇 때문에 잘 풀지 못하고 고민했던거 같다. 치즈가 녹는 문제의 성질을 이해 했다는 가정하에 이 문제의 핵심은 "가장 자리"에 있는 치즈들만 녹일 수 있게 코드를 만들어야 했다. 안쪽에 있는 치즈는 녹지 않기때문에 일반적으로 치즈를 상대로 bfs() 를 진행 했다면 안쪽에 치즈까지 건들기 때문에 생각에 발상을 조금 바꾸어야 했다.
가장 처음에 치즈를 입력받게 되면은 모든 구간을 -1로 바꾸어 주었다. 그리고 bfs() 를 진행 했던건 치즈가 아니고 "공기" 를 대상으로 탐색을 했고 만약에 -1을 탐색했다면 이 부분은 치즈가 확실함으로 더 이상 탐색을 진행하지 않고 녹여야 하는 치즈 숫자에 +1을 해주었다. 그렇게 탐색을 하다보면은 결국에 모든 치즈가 녹아 내렸을거고 air 와 answer 을 출력해서 모든 테스트 케이스를 통과했다.
#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100010
using namespace std;
int N, M;
int matrix[101][101];
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
vector<pair<int,int>> cheeseArea;
void Input(){
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> matrix[i][j];
if(matrix[i][j] == 1){
cheeseArea.push_back({i,j});
matrix[i][j] = -1;
}
}
}
}
void bfs(int x, int y, int& air, int& surround){
queue<pair<int,int>> q;
q.push({x,y});
matrix[x][y] = air;
while(!q.empty()){
int size = q.size();
for(int i = 0; i < size; i++){
pair<int,int> first = q.front();
q.pop();
int currX = first.first, currY = first.second;
for(pair<int,int>& p : dir){
int nX = currX + p.first;
int nY = currY + p.second;
if(nX < 0 || nY < 0 || nX >= N || nY >= M || matrix[nX][nY] == air) continue;
if(matrix[nX][nY] == -1){
matrix[nX][nY] = air;
surround++;
continue;
}
matrix[nX][nY] = air;
q.push({nX,nY});
}
}
}
}
void Solution(){
int air = 1, currCheese = cheeseArea.size(),surround = 0;
int answer = 0;
while(currCheese > 0){
bfs(0,0,air,surround);
answer = currCheese;
currCheese -= surround;
air++;
surround = 0;
}
cout << air - 1<< endl;
cout << answer;
}
void Solve(){
Input();
Solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("input.txt", "r", stdin);
Solve();
return 0;
}