[C++] 백준 2638번: 치즈 (구현)

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

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

규칙에 따라 치즈가 녹을 때, 모든 치즈가 녹아 없어지는데 걸리는 시간을 구하여라.

 

 치즈가 녹는 규칙은 다음과 같습니다.

매 시간마다, 외부 공기와 두 면 이상 접촉한 치즈가 녹아 사라진다.

---

시간복잡도 어림하기

 미리 시간복잡도를 어림하는 것이 큰 의미가 없는 구현 문제이므로 생략하겠습니다.

---

알고리즘 설계하기

 이 문제의 핵심은 치즈가 녹을 때 '외부' 공기와 2면 이상 접촉한 치즈가 녹는 것입니다. 다시 말해, 외부 공기와 내부 공기를 구분할 수 있어야 합니다.

 

 외부 공기를 판단할 수 있는 가장 단순한 방법은 DFS를 활용하는 것입니다. 문제의 조건 중 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 간주한다."라는 조건이 있으므로 (0, 0)을 시작으로 탐색을 진행하면 됩니다.

 

 (0, 0)은 반드시 외부 공기이므로 (0, 0)에서 공기를 통해 이동할 수 있는 모든 위치는 외부 공기라고 할 수 있습니다. 또한, 탐색 중 만나는 치즈는 외부 공기와 접촉해 있다고 볼 수 있습니다. 따라서 외부 공기를 판단하는 동시에 어떤 치즈가 두 면 이상 접하고 있는지도 함께 판단합니다.

 

 어떤 치즈가 외부 공기와 몇 면으로 접촉하고 있는가는 visited 배열을 활용하여 구할 수 있습니다. 이 DFS는 공기가 있는 위치로만 이동하지만, 치즈를 만난다면 해당 위치의 vistied 값을 1 증가시킵니다. 이는 해당 위치를 방문했다는 의미이지만, 실제로 해당 위치로 이동하면 안 되므로 해당 위치로 재귀호출은 하지 않습니다.

 

코드로는 다음과 같이 표현할 수 있습니다.

void dfs(int y, int x){ //(y, x)는 이미 방문체크가 된 상태
    for(int i = 0; i < 4; i++){
        /*다음 위치 ny, nx 계산 및 유효성 검사*/
        if(다음 위치가 공기이고 아직 방문하지 않았다면){
            visited[ny][nx] = 1;
            dfs(ny, nx);
        }
        if(다음 위치가 치즈라면){
            visited[ny][nx]++;
            if(visited[ny][nx] == 2) //두 면이 외부 공기와 접촉 중
                제거 대상으로 저장
        }
    }
}

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int n, m, a[104][104], visited[104][104], ret;
vector<pair<int, int>> v;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
void dfs(int y, int x){ //(y, x)는 이미 방문처리 됨
    for(int i = 0; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        /*아직 방문하지 않은 공기 -> 방문*/
        if(a[ny][nx] == 0 && visited[ny][nx] == 0){
            visited[ny][nx] = 1;
            dfs(ny, nx);
        }
        /*외부 공기와 접촉한 치즈*/
        if(a[ny][nx] > 0){
            visited[ny][nx]++;
            if(visited[ny][nx] == 2) //외부 공기와 두 면이 접촉한 경우
                v.push_back({ny, nx}); //삭제할 치즈 위치 저장
        }
    }
}

/*모든 치즈가 녹았는지 확인*/
bool isEnd(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(a[i][j] == 1) return false;
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) cin >> a[i][j];
    }
    
    /*(0, 0) 방문 처리 및 dfs 실행*/
    visited[0][0] = 1;
    dfs(0, 0);
    while(!isEnd()){ //매 시행마다 남은 치즈가 있는지 확인
        ret++;
        for(auto pos : v) //v에 담긴 치즈 제거
            a[pos.first][pos.second] = 0; 

        /*이전 정보 초기화*/
        memset(visited, 0, sizeof(visited));
        v.clear();
        
        dfs(0, 0);
    }
    cout << ret;
    return 0;
}

 위 코드는 whlile 루프를 모든 치즈가 사라질 때까지 반복하면서 모든 치즈가 사라지는 시간을 구하는 코드입니다. while 루프에 들어가기전 dfs를 한 번 실행하여 모든 치즈가 사라졌는지 확인한 후 while 루프에 진입합니다.

 

 모든 치즈가 사라졌는지 확인하는 로직은 아주 단순합니다. 2차원 배열의 모든 값이 0인지만 확인하면 됩니다.

 

 while 루프에서는 이전에 dfs를 실행한 정보가 남아있으므로 해당 정보를 바탕으로 삭제할 치즈를 제거합니다. 이후 이전 방문 정보와, 삭제 치즈 정보를 초기화하여 dfs를 다시 실행합니다.

---