https://www.acmicpc.net/problem/2638
2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로
www.acmicpc.net
[문제 요약]
- N x M의 모눈종이 위에 아주 얇은 치즈가 아래 그림과 같이 표시되어있다.
- 이 치즈는 공기와 접촉하면 천천히 녹는다.
- 모눈종이 모양의 치즈에서 각 치즈 격자(작은 정사각형 1칸)의 4변 중 적어도 2개의 변이 공기와 접촉하면 한 시간뒤 녹아 없어진다.
- 아래 그림과 같이 C로 표시된 치즈조각이 녹게 된다.
- 아래 그림과 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않은 것으로 가정한다.
- 하지만 이 공간으로 외부 공기가 유입되면 외부 공기와 같은 것으로 간주된다.
- 모눈종이 가장자리에는 치즈가 놓이지 않는 것으로 가정할때, 치즈가 모두 녹아 없어지는 시간을 구하여라
[문제 조건]
- 첫째 줄에는 모눈종이의 크기를 나타내는 두개의 정수 N, M ( 5 ≤ N, M ≤ 100 )이 주어진다.
- 그 다음 N개의 줄에는 모눈종이 위에 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다.
- 시간 제한 : 1초
- 메모리 제한 : 128MB
[문제 설명]
이 문제는 저번에 풀었던 문제와 아주 유사하다. https://tobrother.tistory.com/4
하지만 저번 문제와는 달리, 치즈조각이 공기와 닿으면 없어진다라는 조건에 2변이 외부공기와 접촉하는 치즈만 녹는다라는 조건이 추가된다.
아니 그러면 저번 코드에 2번 닿은 치즈만 없애는 코드만 추가하면 되지않나? 라는 생각을 할 수 있다. 물론 이 방법도 가능하다. 하지만 필자는 다른 방법으로 한번 구현해봤다.
저번 코드는 외부공기에서 탐색을 진행하여 치즈를 나타내는 1을 만나면 제거하는 방법을 사용했다. 그러나 이번 문제에서는 외부공기가 중점이 아니라 치즈를 중점으로 탐색을 진행했다.
처음에 먼저 외부공기와 내부공기를 구분지었다. 왜냐하면 치즈조각 관점에서 4방향을 확인했을때 내부공기와 외부공기를 구분할 필요가 있었기 때문이다.
문제에서 주어진 예제를 이용해 나타내면, 위 그림이 초기상태의 그림이다. 여기서 외부공기와 내부 공기를 구별하면 아래 그림이 된다.
외부공기는 초기에 -1로 저장했다.
그다음 치즈들을 확인하면서 cheese_value를 이용하여 삭제될 치즈와 살아남을 치즈를 구분 지었다. 처음에 cheese_value값은 2로 초기화되어 있고 이 값은 전체적으로 탐색이 끝난 후 1씩 증가한다.
한 번의 탐색이 끝나면 살아 남은 치즈들은 2로 바뀌고 삭제될 치즈들은 -2로 바뀐다. 아래 그림을 확인해보자
위 그림에서 살아남은 치즈들은 파란색으로 표시했다. 여기서 내부공기들돌 치즈가 사라짐에 따라 사라진 치즈들과 같은 값으로 갱신하여 외부공기와 같다고 인식할 수 있게 음수로 표기했다.
이때 내부공기를 바꾸는 기준은 삭제될치즈의 주변에 내부공기가 존재한다면 내부공기의 좌표를 저장해둔 다음 DFS or BFS를 이용하여 값을 갱신했다.
위 방법을 계속해서 반복하여 진행하여, 만약 바꿀 치즈가 없는 경우 종료시킨 뒤 걸린 시간을 출력한다.
[소스 코드1]
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <queue>
using namespace std;
int n, m, cheese_value = 2;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<vector<int>> mp;
void DFS(int y, int x, int value)
{
mp[y][x] = value;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (mp[ny][nx] == 0) DFS(ny, nx, value);
}
}
void BFS(int y, int x)
{
queue<pair<int, int>> q;
q.push({ y,x, });
while (!q.empty())
{
pair<int, int> tmp = q.front(); q.pop();
int dac = 0;
queue<pair<int,int>> vacuum;
for (int i = 0; i < 4; i++)
{
int nx = tmp.second + dx[i];
int ny = tmp.first + dy[i];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (mp[ny][nx] <= -1 && mp[ny][nx] >= -(cheese_value - 1)) dac++;
else if (mp[ny][nx] == cheese_value - 1) { mp[ny][nx] = cheese_value; q.push({ ny,nx }); }
else if (mp[ny][nx] == 0) vacuum.push({ ny,nx });
}
if (dac >= 2)
{
mp[tmp.first][tmp.second] = -cheese_value;
while (!vacuum.empty())
{
pair<int, int> tmp2 = vacuum.front(); vacuum.pop();
DFS(tmp2.first, tmp2.second, -cheese_value);
}
}
else mp[tmp.first][tmp.second] = cheese_value;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
mp.resize(n);
for (int i = 0; i < n; i++) mp[i].resize(m);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> mp[i][j];
queue<pair<int, int>> q;
q.push({ 0,0 });
mp[0][0] = -1;
while (!q.empty())
{
pair<int, int> tmp = q.front(); q.pop();
for (int i = 0; i < 4; i++)
{
int nx = tmp.second + dx[i];
int ny = tmp.first + dy[i];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (mp[ny][nx] != 0) continue;
if(mp[ny][nx]== 0) q.push({ ny,nx });
mp[ny][nx] = -1;
}
}
bool f_flag = true;
int ans_cnt = 0;
while (f_flag)
{
int tmp_cnt = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mp[i][j] != cheese_value - 1) continue;
BFS(i, j);
tmp_cnt++;
}
}
cheese_value++;
if (tmp_cnt == 0)break;
ans_cnt++;
}
cout << ans_cnt;
}
위 방법을 이용하여 정답에 성공하긴했다. 하지만 맘에 걸렸던 부분이 바로 걸린 시간이다. 뭔가 오래걸린 듯한 느낌을 받아 다른 아이디어로 한번 다시 풀어보기로 했다.
먼저 외부공기와 내부공기를 구분짓는건 필수적으로 해야될 것 같아. 이 부분에 대해서 딱히 수정이 없었다.
그 다음으로 격자판을 차례로 확인하면서 치즈를 만나면 BFS를 도는 것이 아니라. 그 치즈가 삭제될 치즈인가? 아닌가?만 판별하고 만약 삭제될 치즈라면 큐에 집어 넣어 나중에 한꺼번에 외부 공기로 바꿔주는 방법을 생각했다. 이 방법을 이용한 코드가 밑에 있다.
[소스 코드2]
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <queue>
using namespace std;
int n, m, cheese_value = 2;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
vector<vector<int>> mp;
queue<pair<int, int>> vacuum;
void DFS(int y, int x, int value)
{
mp[y][x] = value;
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (mp[ny][nx] == 0) DFS(ny, nx, value);
}
}
void divide()
{
queue<pair<int, int>> q;
q.push({ 0,0 });
mp[0][0] = -1;
while (!q.empty())
{
pair<int, int> tmp = q.front(); q.pop();
for (int i = 0; i < 4; i++)
{
int nx = tmp.second + dx[i];
int ny = tmp.first + dy[i];
if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
if (mp[ny][nx] != 0) continue;
if (mp[ny][nx] == 0) { q.push({ ny,nx }); mp[ny][nx] = -1; }
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
mp.resize(n);
for (int i = 0; i < n; i++) mp[i].resize(m);
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> mp[i][j];
divide();
bool f_flag = true;
int ans_cnt = 0;
while (f_flag)
{
int tmp_cnt = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mp[i][j] == 1)
{
int dac = 0;
for (int r = 0; r < 4; r++)
{
int nx = j + dx[r];
int ny = i + dy[r];
if (mp[ny][nx] == -1) dac++;
}
if (dac >= 2) vacuum.push({ i,j });
tmp_cnt++;
}
}
}
while (!vacuum.empty())
{
pair<int, int> tmp = vacuum.front(); vacuum.pop();
DFS(tmp.first, tmp.second, -1);
}
if (tmp_cnt == 0) break;
ans_cnt++;
}
cout << ans_cnt;
}
이 방법 말고 소스코드1을 개량해서 여러 방법을 시도했지만 오히려 시간이 더 걸리는 불상사가 생기기도 했다.
소스코드1과 소스코드2의 시간차이가 나는 이유는 아마도 치즈를 만나자마자 탐색을진행 or 나중에 한꺼번에 모아서 진행 의 차이인 것 같다.
굳
'BOJ 풀이' 카테고리의 다른 글
| [BOJ/백준 1516/C++] 게임 개발 (1) | 2022.12.06 |
|---|---|
| [BOJ/백준 17142/C++] 연구소 3 (0) | 2022.12.05 |
| [BOJ/백준 2146/C++] 다리 만들기 (0) | 2022.12.02 |
| [BOJ/백준 14890/C++] 경사로 (0) | 2022.12.01 |
| [BOJ/백준 1937/C++] 욕심쟁이 판다 (2) | 2022.11.30 |