https://www.acmicpc.net/problem/2636
문제
> 아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고,
그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다.
> 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
> 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다.
> 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다.
> <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
> 다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
> <그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며,
남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다.
> 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다.
> <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
> 입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때,
공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
접근
그래프 탐색을 이용하고 해줘야할 기능은 3가지가 있다.
1. 구멍 찾기
전체를 돌며 입력이 0인 각 덩어리들을 보는데 덩어리 중 하나라도 틀의 가장자리인 (0, y), (N-1, y), (x, 0), (x, M-1)좌표가 있다면 구멍이 아닌거고 하나도 없으면 구멍인 것이다. 여기서 구멍이라고 나오면 0으로 왔던 구멍을 2로 표시해준다.
2. 녹을 치즈 찾기
입력이 1인 치즈들만 돌며 탐색하는데 큐에서 꺼내와 현재 보고있는 치즈의 좌표(fr, fc)의 사방탐색 결과(nr, nc) 중 하나라도 0(공기가 통하는 빈칸)이라면 녹을 치즈 대기열 벡터에 (fr, fc)를 저장하고 수를 누적하며 0으로 만들어준다.
3. 틀 재정렬
치즈가 녹았으면 구멍이었던 2 부분이 틈이 생겨 0과 만나 공기가 통하게 될 수도 있다. 따라서 치즈를 제거하고 난 뒤 2였던 좌표를 잡아와서 그래프 탐색으로 쭉 탐색한다. 하나라도 사방에 0이 있다면 공기가 통하므로 2였던 애들을 모두 0으로 만들어준다.
그래서 이 세가지 기능을 이용해 처음 치즈 틀이 들어오면 구멍찾기로 구멍을 찾아주고 while문으로 녹을 치즈찾기(+녹이기)와 틀 재정렬을 반복해준다.
틀 재정렬 기능에서 2를 기준으로 탐색을 돌지만 2인지 확인하기 전에 일단 1인지 확인해서 틀에 치즈가 있나 없나를 본다.
있다면 또 녹여야하므로 반복이고 없다면 녹을게 없어서 이를 부울값으로 전달해 while문을 깨준다.
문제해결
> 틀의 행 N, 열 M 그리고 상방탐색의 좌표 변화 상하좌우 정의해준다.
> 치즈판을 나타내는 cheese벡터, 그래프탐색의 방문처리를 위한 visited벡터를 만들어준다.
> 치즈 찾기 기능에서 누적할 녹을 치즈 수인 Ccnt와 녹는데 걸린시간인 Mcnt를 선언한다.
> 구멍 뚫기 및 틀 재정렬 함수인 Hole을 정의한다.
> 좌표쌍을 입력으로 받아 큐에 넣고 시작하며 tmp벡터를 통해 들어온 좌표와 연결된 덩어리들을 모두 저장해둔다.
> while문에서 큐에서 꺼낸 현 좌표가 틀의 가장자리(공기통함)인지 확인하고 맞다면 hole 부울값을 false로 준다.
> false가 주어지면 공기가 통해서 0으로 되야하므로 아래 while문 깨진 이후 tmp에 있는 좌표들의 값이 0으로 바뀐다.(틀 재정렬 기능)
> true로 그대로 간다면 공기가 안통하므로 아래에서 전부 2로 바꿔준다.(구멍 뚫기)
> 사방탐색으로 다음 칸을 탐색해 치즈가 없는 위치만 따져 큐에 넣어준다.
> 녹을 치즈 찾는 Melt함수를 정의한다.
> 좌표쌍을 입력으로 받고, 녹을 치즈들을 저장할 melt벡터를 선언해준다.
> 녹을 치즈인지 아닌지 판단하는 melting 부울 변수를 일단 false로 시작하고 사방탐색을 하며 큐에서 꺼내 현재 보고있는 fr,fc에 대한 사방의 nr,nc중 하나라도 0이 있다면 공기가 녹아야 하므로 true로 바꿔주며 사방 탐색이 끝난 뒤 이 부울 값에 따라 melt벡터에 저장할지 말지 따져준다.
> 없다면 그대로 false로 나와 녹지 않는 치즈로 판정된다.
> while문이 끝나고 melt벡터에 있는 좌표들을 꺼내와서 몇개인지 누적하고, 이 좌표들의 값을 0으로 바꿔 녹았다 라고 처리해준다.
> 이제 main함수에선 입력으로 들어온 치즈틀을 입력받고 먼저 구멍 뚫기 메소드를 호출해 구멍을 뚫어준다.
> while문으로 녹을치즈 탐색, 치즈틀 재정렬을 반복한다.
제대로된 탐색을 위해 치즈탐색, 재정렬 전 방문처리를 초기화 해주고
모든 녹을 치즈를 누적하기 위해 치즈 탐색 전에 0으로 초기화해 한 시간마다 녹을 애들의 수가 바뀌도록 해준다.
> 재정렬기능에서 틀에 1인 치즈가 안남아 false가 전달되면 다 녹은것이므로 깨고 나와 녹는데 걸린 시간 Mcnt와 마지막에 남은 치즈 수 Ccnt를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N, M;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
vector<vector<int>> cheese;
vector<vector<bool>> visited;
int Ccnt = 0, Mcnt = 0;
void Hole(pair<int, int> b) //0만 입력 넣기
{
queue<pair<int, int>> q;
q.push(b);
visited[b.first][b.second] = true;
vector<pair<int, int>> tmp;
bool hole = true;
while (!q.empty())
{
int fr = q.front().first;
int fc = q.front().second;
q.pop();
if (fr == 0 || fr == N - 1) hole = false;
if (fc == 0 || fc == M - 1) hole = false;
tmp.push_back({fr, fc});
for (int i = 0; i < 4; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
if (nr < 0 || nr >= N) continue;
if (nc < 0 || nc >= M) continue;
if (cheese[nr][nc] == 1) continue;
if (!visited[nr][nc])
{
q.push({ nr, nc });
visited[nr][nc] = true;
}
}
}
if (hole)
{
for (auto a : tmp)
{
cheese[a.first][a.second] = 2;
}
return;
}
else
{
for (auto a : tmp)
{
cheese[a.first][a.second] = 0;
}
return;
}
}
void Melt(pair<int, int> m)
{
queue<pair<int, int>> q;
q.push(m);
visited[m.first][m.second] = true;
vector<pair<int, int>> melt;
while (!q.empty())
{
int fr = q.front().first;
int fc = q.front().second;
q.pop();
bool melting = false;
for (int i = 0; i < 4; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
if (nr < 0 || nr >= N) continue;
if (nc < 0 || nc >= M) continue;
if (cheese[nr][nc] == 0) melting = true;
if (cheese[nr][nc] != 1) continue;
if (!visited[nr][nc])
{
q.push({ nr, nc });
visited[nr][nc] = true;
}
}
if(melting) melt.push_back({ fr, fc });
}
if (!melt.empty())
{
Ccnt += melt.size();
for (auto a : melt)
{
cheese[a.first][a.second] = 0;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
cheese.resize(N, vector<int>(M));
visited.assign(N, vector<bool>(M, false));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> cheese[i][j];
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (cheese[i][j] != 0) continue;
if (visited[i][j]) continue;
Hole({ i,j });
}
}// 구멍 2로 바꾸기
while (1)
{
visited.assign(N, vector<bool>(M, false)); //구멍 탐색 끝났으니 방문초기화
Ccnt = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (cheese[i][j] != 1) continue;
if (visited[i][j]) continue;
Melt({ i, j });
}
} // 가생이 치즈 탐색해서 3으로 만들어줌
Mcnt++;
visited.assign(N, vector<bool>(M, false)); //방문초기화, 구멍이 아직도 구멍인지 확인
bool again = false;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
if (cheese[i][j] == 1) again = true;
if (cheese[i][j] != 2) continue;
if (visited[i][j]) continue;
Hole({ i,j });
}
} //더이상 구멍이 아니면 0으로 만들어줌(공기 통함)
if (!again) break;
}
cout << Mcnt << '\n';
cout << Ccnt << '\n';
}
후기
내가 짠 구조에 따라 하나 하나 전부 출력하며 흐름을 확인해 가며 했다. 큰 틀을 잡아놓고 각각의 기능을 만든 뒤 while문을 쓰기 전에도 다 출력을 찍어보고 했다. 오래걸렸지만 원트에 맞아 좋다.
