My Profile

김형훈

안녕하세요.
김형훈입니다.

백준 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