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

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.


<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
📕입력
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.
📕출력
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
🔎문제 해석
외부 공기와 내부 공기를 분리시키는 작업이 중요한 문제이다.
내부 공기는 치즈에 영향을 주지 않지만, 외부 공기는 치즈에 영향을 주기 때문이다.
공기를 구분 한뒤 그 외부 공기와 맞닿은 지역을 녹이는 작업을 계속하면 된다.
나는 BFS를 사용해서 풀었다.
💡초기 풀이 방식
- 입력받은 배열중 0은 공기, 1을 치즈라고 생각했다.
- 치즈에 해당하는 부분은 queue에 푸쉬했다.
- 그다음에 bfs를 돌렸다.
🛑문제점
- 내부 공기와 외부 공기를 분리를 시키지 않아서 문제가 풀리지 않았다.
💡수정 풀이 방식
- 외부 공기와 내부 공기를 구분했다.
- 내부 공기는 치즈에 영향을 주지 않기 때문이다.
- 배열을 입력받는 과정에서 만약 그 위치가 치즈라면[값이 1이라면] 그 좌표에 대한 visit값을 0으로 세팅해주고, queue에 넣어주고, 치즈의 조각을 +1 해줌.
- 초기 치즈의 조각도 계산해줄 필요가 있다. [아예 녹일 수 없는 상황이라면 그 초기의 치즈 개수가 최종 치즈의 개수이기 때문이다.] -> 이것은 문제를 풀다 보면 이해할 수 있을 것이다. 마지막 테케가 아예 녹이지 못하게 되는 경우라서 꼭 이 작업을 해줘야 한다!
- visit배열을 새로 만들었다. [초기 값은 내부 공기에 해당하는 값을 세팅해줌]
- 세팅 값 : 2=내부 공기, 1 = 외부 공기, 0 = 치즈
- 내부 공기를 뽑는 방법은 (0,0)에서 출발해서 0으로만 이동을 쭉쭉한다. [BFS 사용]
- 외부 공기와 인접하는 치즈들을 녹이는 작업을 시작한다.
- 기본적으로는 BFS 작업.
- 상하좌우로 이동한 뒤 적절한 이동이고, 근처에 좌표 중 하나라도 공기가 있다면 치즈를 녹임
- 녹인 뒤 시간을 +1 해준다.
- 사용한 queue를 초기화해주고, visit 배열도 다시 초기화해준다.
- 그리고 다시 2,3,4,5,6,7 작업을 반복한다.
- 그러다가 만약 모든 배열에 값이 0이라면 [치즈가 다 녹았다면] 빠져나와서 결과값을 출력함.
💻코드
/*
2306 골드4 치즈
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, m;
vector<vector<int>> graph;
vector<vector<int>> visit;
queue<pair<int, int>> q;
queue<pair<int, int>> chese;
vector<pair<int, int>> air;
vector<int> x = {0, 0, 1, -1};
vector<int> y = {1, -1, 0, 0};
int t = 0, piece = 0, number = 0, result;
void outside_air();
void melting();
bool check();
int main()
{
cin >> n >> m;
graph.resize(n, vector<int>(m, 0));
visit.resize(n, vector<int>(m, 2));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> graph[i][j];
if (graph[i][j] == 1)
{ //치즈 위치를 queue에 넣음.
q.push(make_pair(i, j));
piece++;
visit[i][j] = 0; //치즈는 0으로 초기화.
}
}
}
// graph랑 visit 배열 설정 위에서햇음.
while (1)
{
if (check() == true)
{ //전부다 공기라면 반복문을 멈춘다.
break;
}
result = piece;
piece = 0;
outside_air(); //외부공기를 visit값을 1로 초기화
melting(); //외부공기와 맞닿은 치즈를 녹여줌. 해당 좌표를 graph 0값으로 돌림.
t++; //녹였으면 t++해줌.
//녹이고 치즈 개수 세야함.
while (!q.empty())
{ // queue 초기화.
q.pop();
}
visit.assign(n, vector<int>(m, 2));
for (int i = 0; i < n; i++)
{ // visit 배열에서 치즈 위치를 queue에 넣고, 치즈 위치를 visit에서 0으로 초기화
for (int j = 0; j < m; j++)
{
if (graph[i][j] == 1)
{
piece++; //치즈 기록.
q.push(make_pair(i, j));
visit[i][j] = 0;
}
}
}
}
cout << t << endl; //다 녹인 시점 전에 시간을 출력
cout << result; //그 시간대에 치즈 조각들을 출력
}
bool check() //배열에서 치즈가 다 녹았는지 안녹았는지 체크를 해줌.
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (graph[i][j] == 1)
{ //치즈가 있다면
return false;
}
}
}
return true;
}
void outside_air() //외부 공기를 솎아 내는 작업
{
queue<pair<int, int>> out;
out.push(make_pair(0, 0)); //초기 좌표 넣어줌.
while (!out.empty())
{
int tx = out.front().first;
int ty = out.front().second;
// cout<<"현재 좌표 : "<<tx<<" "<<ty<<endl;
out.pop();
for (int i = 0; i < 4; i++)
{
int row = tx + x[i];
int col = ty + y[i];
// cout<<"move :"<<row<<" "<<col<<endl;
if (row < 0 || col < 0 || row >= n || col >= m)
{
continue;
}
if (graph[row][col] == 0 && visit[row][col] == 2)
{ //갈려는 곳이 치즈가 아니고, 아직 방문 안했던 곳이라면
out.push(make_pair(row, col));
visit[row][col] = 1; //외부 공기는 1로 초기화.
}
}
}
}
void melting() //외부공기랑 맞닿은 지역을 녹이기.
{
queue<pair<int, int>> melt = q; // melt에는 치즈가 들어있음.
while (!melt.empty())
{
int mx = melt.front().first;
int my = melt.front().second;
melt.pop();
// chese 초기 위치 뽑아줌.
for (int i = 0; i < 4; i++)
{ //좌표 이동
int tempx = mx + x[i];
int tempy = my + y[i];
if (tempx < 0 || tempy < 0 || tempx >= n || tempy >= m)
{
continue;
}
if (visit[tempx][tempy] == 1)
{ //외부 공기와 맞닿아있다면
graph[mx][my] = 0; // graph상에서 치즈를 공기로 바꿔줍니다.
}
}
}
}
✔느낀 점
- 신선한 문제였다.
- 100%에서 틀리길래 뭔가 했는데 모든 배열이 1111111111111111111 즉 치즈로 채워진 경우에는 내가 생각을 안 해줘서 100%에서 틀린 거 같다.
- BFS는 이제 좀 할만할지도..?
'CodingTest > Baekjoon' 카테고리의 다른 글
| [백준 16174] - 점프왕 쩰리(Large) (1) | 2022.11.12 |
|---|---|
| [백준 2206] - 벽 부수고 이동하기(C++) (0) | 2022.11.11 |
| [백준 9205] - 맥주 마시면서 걸어가기(C++) (0) | 2022.11.10 |
| [백준 1325]-효율적인 해킹(C++) (0) | 2022.11.08 |
| [백준 5052] 전화번호 목록(C++) (0) | 2022.10.06 |