반응형
https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
접근방법[알고리즘]
1. 빙산이 몇개의 덩어리로 이루어져있는지 BFS를 이용해 개수를 센다.
2. 빙산의 개수가 2개이상이거나 0이 아니면 빙산을 한차례 녹인다.
3. 1과 2를 반복한다.
주의할 점
빙산이 녹아 없어지는 경우 바로 0으로 만들어버리면
다음 빙산에 영향을 줘서 틀린다.
빙산이 0이 되는 경우는 따로 저장해뒀다가 큐를 한바퀴 다 돈다음
적용 해주어야 한다.
문제풀이코드 C++
#include <bits/stdc++.h>
using namespace std;
int n, m, arr[301][301] ,t;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int Count() {
int check[301][301];
int ans = 1;
memset(check, 0, sizeof(check));
queue<pair<int, int> > Q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] > 0 && check[i][j]==0) {
check[i][j] = ans;
Q.push({ i,j });
while (!Q.empty()) {
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] == 0) continue;
if (check[nx][ny] == 0) {
check[nx][ny] = ans;
Q.push({ nx,ny });
}
}
}
ans++;
}
}
}
return ans - 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
queue<pair<int, int> > Q;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] > 0) Q.push({ i,j });
}
}
while (1) {
int area = Count();
if (area >= 2) {
cout << t << '\n';
return 0;
}
else if (area == 0) {
cout << 0 << '\n';
return 0;
}
int s = Q.size();
//빙산이 녹아 없어지는 경우 바로 0으로 만들어버리면
//다음 빙산에 영향을 줘서 틀린다.
//빙산이 0이 되는 경우는 따로 저장해뒀다가 큐를 한바퀴 다 돈다음
//적용 해주어야 한다.
vector<pair<int, int> > melt;
for (int i = 0; i < s; i++) {
int x = Q.front().first;
int y = Q.front().second;
Q.pop();
int cnt = 0;
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny]>0) continue;
cnt++;
}
if (cnt >= arr[x][y]) {
melt.push_back({ x,y });
}
else {
arr[x][y] -= cnt;
Q.push({ x,y });
}
}
for (int i = 0; i < melt.size(); i++) {
arr[melt[i].first][melt[i].second] = 0;
}
t++;
}
return 0;
}
반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 10800 : 컬러볼 누적합, 투포인터 활용 C++ (0) | 2022.02.14 |
|---|---|
| 백준 10166번: 관중석 문제풀이코드 C++ (0) | 2022.02.13 |
| 백준 15971번: 두 로봇 C++ 문제풀이코드 (0) | 2022.02.13 |
| 백준 2636번 : 치즈 BFS C++ (0) | 2022.02.13 |
| 백준 1753번 : 최단 경로 - 다익스트라 C++ 코드 (0) | 2022.02.13 |
