[백준] 치즈

유승선 ·2022년 10월 26일
0

백준

목록 보기
61/64

분명히 쉬운 문제인데 생각보다 좀 고전했다. 복잡하게 생각하는 내 버릇 때문에 잘 풀지 못하고 고민했던거 같다. 치즈가 녹는 문제의 성질을 이해 했다는 가정하에 이 문제의 핵심은 "가장 자리"에 있는 치즈들만 녹일 수 있게 코드를 만들어야 했다. 안쪽에 있는 치즈는 녹지 않기때문에 일반적으로 치즈를 상대로 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;
}
profile
성장하는 사람

0개의 댓글