[C++] 백준 2638 : 치즈

문제

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

 

 

 

풀이

모든 치즈가 녹을 때까지 다음 과정을 반복한다.

1. 외부 영역과 내부 영역을 구분(DFS 또는 BFS 이용. 나의 경우 DFS를 이용함.)
2. 현 상태에서 녹을 수 있는 치즈인지 아닌지를 구분.
3. 만약 녹을 수 있는 치즈라면, 녹임. 이때 녹을 수 있다 =  2면 이상이 외부 영역과 접촉.
4. 모든 치즈를 녹인 후 소요시간 증가
5. 배열 초기화

 

이 문제를 풀 때 가장 고민했던 부분은 우선 내부 영역을 어떻게 구분할지였다. 하지만 문제에서 외곽은 항상 비어 있기 때문에, (0,0)에서 DFS를 돌리면 항상 외부 영역과 내부 영역을 구분할 수 있다. 

내부 -> 외부 방향이 아닌, 외부-> 내부 방향으로 외부 영역과 내부 영역을 구분한다.

 

 

 또 매 time stamp 마다 DFS(또는 BFS)를 돌려서 갱신된 외부 영역과 내부 영역을 구분해야 한다. 배열의 최대 크기가 작으므로 시간 초과는 발생하지 않는다.

 

 아래의 코드에서 필요없는? 부분도 있어서 전체적인 구현 방식만 참고해도 될 것 같다!

 

 

코드

#include <iostream>
using namespace std;

int n, m, num_cheese; // n 세로, m 가로 
int arr[100][100];
int visited[100][100]; // 방문 표시 배열
int external[100][100]; // 외부 공기인가?
int melt[100][100]; // 녹을 수 있는가?

int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};

struct State{
    int y, x;
};

void DFS(int y, int x){
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if(ny <0 || ny >=n || nx < 0 || nx >=m ) continue;
        if(visited[ny][nx] == 1) continue;
        if(arr[ny][nx] == 1) continue;
        external[ny][nx] = 1;
        visited[ny][nx] = 1;
        DFS(ny, nx);
    }
    return;
}

int change(int y, int x){
    int ans=0;
    int ext = 0;
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(arr[ny][nx] == 0 && external[ny][nx]==1) melt[y][x]++;
    }
    
    if(melt[y][x] >=2) return 1;
    return 0;
}

int main()
{
   cin >> n >> m;
   for(int i=0; i<n; i++){
       for(int j=0; j<m; j++){
           cin >> arr[i][j];
           if(arr[i][j] == 1) num_cheese++;
       }
   }

   int r = 0;
   while(num_cheese>0){
       // 배열 초기화 
       for(int i=0; i<n; i++){
           for(int j=0; j<m; j++){
               visited[i][j] = 0;
               external[i][j] = 0;
               melt[i][j] = 0;
           }
        }
        
        //외부 영역 칠하기 
        visited[0][0] = 1;
        DFS(0,0);
        
        // 녹을 수 있는 치즈 표시 
        for(int i=0; i<n; i++){
           for(int j=0; j<m; j++){
               if(arr[i][j] == 1){
                   int ans = change(i,j);
                   
                   // 녹을 수 있다면, 
                   if(ans == 1){
                       arr[i][j] = 0; // 녹이기 
                       num_cheese--; // 남은 치즈 개수 줄이기 
                   }
               }
           }
        }
        
        // 소요 시간 늘리기 
        r++;
   }

    cout << r << "\n";

    return 0;
}

 

 

---

 

메모

내부만 칠하는 것보다 외부를 칠하는 것이 더 쉽다.. 
내부를 구분한다 = 외부를 구분한다. 결국 동일한 결과.