백준 2638 치즈

문제링크 : https://www.acmicpc.net/problem/2638

아이디어

• 모든 노드 돌면서 주변에 2변 이상 외부 공기에 접촉되어있는지 확인

  • 이럴경우, 안쪽에 있는 공기도 외부공기로 간주되게 됨

• 바깥 공기에 접촉하는지를 확인

  • 0,0부터 bfs 사용해서 이어져있는 공기 먼저 색칠하기
  • 단 계속 확대될 것이기 때문에 원래대로 색칠 안해줘도됨

• 접촉되어있을경우 리스트에 넣었다가 한번에 지우기

• 모두 없어질때까지 반복

시간복잡도 계산

• Flood-fill로 외부공기 확인 : O(NM) = O(N^2)
• 모든 노드 순회 : O(NM) = O(N^2)
• 반복하는 최대상황 : O(N)
  • 가장자리 제외하고 모두 치즈가 꽉찬경우
• 총합 : O((N^2 * N^2) * N) = O(N^3) : 1e6 가능

인트 계산

• 치즈 위치 map : 0,1
• 2변이상 노출시 넣을 벡터 : pair<int, int>
• 없어지는데 걸리는 최대 횟수 : 100

코드(C++)

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int map[110][110];
bool chk[110][110];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    
    // map 먼저 세팅
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    
    // 없어질 치즈
    vector<pair<int, int>> v;
    int t=0;
    while(1) {
        v.clear();
        
        // 바깥 공기 먼저 설정
        fill(&chk[0][0], &chk[109][110], 0);
        queue<pair<int, int>> q;
        q.push(make_pair(0,0));
        chk[0][0] = 1;
        
        
        while(!q.empty()) {
            auto eq = q.front(); q.pop();
            int ey = eq.first;
            int ex = eq.second;
            map[ey][ex] = 2;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                if(ny>=0 && ny<N && nx>=0 && nx< M) {
                    if(chk[ny][nx] == 0 && (map[ny][nx] == 0 || map[ny][nx] == 2)) {
                        chk[ny][nx] = 1;
                        q.push(make_pair(ny, nx));
                    }
                }
            }
        }
        
        // 모든 노드 순회하면서 없어질 치즈 확인
        for(int j=0; j<N; j++) {
            for(int i=0; i<M; i++) {
                if(map[j][i] == 1) {
                    int cnt=0;
                    for(int k=0; k<4; k++) {
                        int ny = j + dy[k];
                        int nx = i + dx[k];
                        if(ny>=0 && ny<N && nx>=0 && nx < M) {
                            if(map[ny][nx] == 2) cnt++;
                        }
                    }
                    if(cnt>=2) v.push_back(make_pair(j,i));
                }
            }
        }
        
        // 없앨 치즈 없을경우 종료
        if(v.empty()) break;
        
        // 치즈 없애기
        for(auto x : v) {
            int ej = x.first;
            int ei = x.second;
            map[ej][ei] = 0;
        }
        
        t++;
    }
    
    cout << t << '\n';
    
    return 0;
}
 

문제유형

• BFS - Flood Fill
  • 이어져있는 노드를 연결하는 문제
  • BFS 사용해서, 이어져 있는 노드 확인

비슷한 문제

• https://www.acmicpc.net/problem/1926
• https://www.acmicpc.net/problem/2638