2638번: 치즈
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표
www.acmicpc.net
1. 풀이방법
- 문제를 보면 bfs를 이용해야 겠다는 생각이 들고,
- 처음에 딱 핵심이다 라고 생각되는 것은 0(빈칸) 중에서 외부공기 / 실내공기 를 나누어 주어야 한다는 것.
- 그리고 문제설정에서 외부공기는 반드시 존재하게끔 되어있습니다.
- 바로 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다" 적어도, 4자리는 외부공기라는 것
- 그래서 처음에 이 4점을 기준으로 bfs를 돌려 외부공기를 모두 2로 표시해주고 시작합니다.
- 저 같은 경우 벡터에 치즈의 자리를 모두 넣은 뒤, 이 치즈들이 사라질 때마다 이 자리들을 다시 큐에 넣어
- 이 치즈가 녹음으로써 내부공기 -> 외부공기 가 되는 것들을 체크해주었습니다.
2. 주의사항
- 이런 류의 문제에서 사라지는 c의 위치를 찾았을 때 바로 ground를 2로 바꿔버리면 그 뒤의 치즈들이 이 것에 의해
- 영향을 받을 수 있습니다. 그래서 벡터의서 check를 true로만 바꿔주고, 작업이 끝난뒤에
- check가 true인 것들을 한번에 2로 바꾸어주었습니다.
3. 나의코드
#include<bits/stdc++.h>
using namespace std;
int n, m;
//1은 치즈 , 0 은 빈칸 , 2는 실외공기
int ground[101][101];
bool visited[101][101];
int cheesecount = 0;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
struct cheese {
int cx, cy;
bool check;
};
vector<pair<int, int>> sideindex;
queue<pair<int, int>> tmpq;
vector<cheese> tmpv;
void inputs() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> ground[i][j];
if (ground[i][j] == 1) {
cheesecount++; tmpv.push_back({ i,j,false });
}
}
}
sideindex.push_back({ 0, 0 }); sideindex.push_back({ n - 1,0 });
sideindex.push_back({ 0,m - 1 }); sideindex.push_back({ n - 1,m - 1 });
}
bool boundcheck(int x, int y) {
if (x >= 0 && x < n && y >= 0 && y < m) return true;
else return false;
}
void makeoutside() {
while (!tmpq.empty()) {
int qsize = tmpq.size();
while (qsize--) {
int nextx = tmpq.front().first;
int nexty = tmpq.front().second;
tmpq.pop();
for (int i = 0; i < 4; i++) {
int tx = nextx + dx[i]; int ty = nexty + dy[i];
if (boundcheck(tx, ty) && visited[tx][ty] == false && ground[tx][ty] != 1) {
visited[tx][ty] = true;
tmpq.push({ tx,ty });
ground[tx][ty] = 2;
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
int second = 0;
//실외공기 구하기
for (int i = 0; i < 4; i++) {
visited[sideindex[i].first][sideindex[i].second] = true;
ground[sideindex[i].first][sideindex[i].second] = 2;
tmpq.push(sideindex[i]);
}
makeoutside();
while (1) {
if (cheesecount == 0) break;
for (int i = 0; i < tmpv.size(); i++) {
if (tmpv[i].check == true) continue;
int vsize = 0;
for (int j = 0; j < 4; j++) { //4방향 탐색
if (ground[tmpv[i].cx + dx[j]][tmpv[i].cy + dy[j]] == 2) {
vsize++;
}
if (vsize >= 2) {
cheesecount--;
visited[tmpv[i].cx + dx[j]][tmpv[i].cy + dy[j]] = true;
tmpv[i].check = true; //여기는 없어짐
tmpq.push({ tmpv[i].cx + dx[j],tmpv[i].cy + dy[j] });
break;
}
}
}
for (int i = 0; i < tmpv.size(); i++) {
if (tmpv[i].check == true) {
ground[tmpv[i].cx][tmpv[i].cy] = 2;
}
}
makeoutside(); //없어진 치즈로 인해 실내공기에서 외부공기가 되는 녀석들 체크
second++;
}
cout << second;
return 0;
}'알고리즘 문제풀이 > DFS와 BFS' 카테고리의 다른 글
| 백준 15900 [C++] (0) | 2021.01.19 |
|---|---|
| 백준 2251 [C++] (0) | 2021.01.19 |
| 백준 1600 [C++] (0) | 2021.01.19 |
| 백준 12851 [C++] (0) | 2021.01.18 |
| 백준 13913 [C++] (0) | 2021.01.18 |