문제 링크

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

문제 설명

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다. 입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

문제 분석

이 문제는 치즈가 녹는 과정을 시뮬레이션하는 문제이다. 주어진 격자에서 치즈는 외부 공기와 접촉한 부분부터 녹기 시작한다. 이를 해결하기 위해, 외부 공기와 접촉한 치즈를 찾아내고 그 치즈를 녹여서 없애는 작업을 반복하는 방식으로 접근한다. 먼저, 주어진 격자에서 치즈와 공기를 구분하여 표시하는데, 치즈는 1, 공기는 0으로 표시된다. 방문 여부를 체크하기 위해 visited 배열을 사용한다. go 함수는 주어진 위치에서 외부 공기와 접촉한 치즈를 찾아내는 함수이다. 이 함수에서 치즈가 발견되면 그 위치를 벡터 v에 저장하고, 그 후에는 인접한 네 방향으로 탐색을 이어가는데 이미 방문한 칸은 다시 방문하지 않도록 visited 배열을 사용한다. go 함수는 재귀적으로 호출되어 치즈와 공기의 경계를 탐색하며 외부 공기와 접촉한 치즈를 찾는다. 치즈가 외부 공기와 접촉했다면 그 위치를 v에 기록하고, go 함수는 종료된다. 치즈를 녹이는 과정은 go(0, 0)을 호출한 후, 벡터 v에 저장된 치즈들의 좌표를 a[b.first][b.second] = 0으로 변경하여 해당 위치의 치즈를 없애는 방식으로 진행된다.

코드

#include <bits/stdc++.h>
using namespace std; 
int a[104][104], visited[104][104];
int dy[] = {-1,0,1,0}, dx[] = {0,1,0,-1};   
int n, m, cnt, cnt2;
vector <pair<int,int>>v;
void go(int y,int x){
    visited[y][x] = 1;
    if(a[y][x] == 1){
        v.push_back({y,x});
        return;
    }
    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 || visited[ny][nx])continue; 
        go(ny,nx);
    }
    return;
}


int main(){ 
    cin >> n >> m; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    while(true){ 
        fill(&visited[0][0], &visited[0][0] + 104 * 104, 0);
        v.clear(); 
        go(0,0); 
        cnt2 = v.size();
        for(pair<int, int> b : v){ 
            a[b.first][b.second] = 0;
        }   
        bool flag = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(a[i][j] != 0) flag = 1;
            }
        }
        cnt++;
        if(!flag) break;
    }
    cout << cnt << '\n' << cnt2 << '\n'; 
}

v벡터에 외부 공기와 접촉된 치즈들의 좌표가 저장이되고, a[b.first][b.second] = 0;을 통해서 치즈를 1 -> 0으로 바꿔주는 것에서 치즈를 지울 수 있었다. 상태변화는 항상 0 -> 1, 1 -> 0으로 만들어주는 아이디어가 핵심이다.

Reference

나의 뇌