2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
빙하가 2차원 배열로 주어지는데 빙하 상하좌우에 0이 있다면 빙하가 0 하나당 -1씩 줄어든다.
구현하면서 신경 쓸만한 부분은 날짜가 지남에 따라 빙하가 녹는 것, 빙하로 이루는 땅이 2개 이상인지 확인할 것
2개만 신경써주면 된다.
if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--;
else if (!vis[nx][ny]) {
q.push({ nx,ny });
vis[nx][ny] = true;
}
상하좌우를 돌면서 방문하지 않았고 0이라면 현재 값을 1 줄여주고
방문하지 않은 빙하라면 큐에 넣어준다.
그리고 갱신해준 후 0 이하라면 0으로 수정해주면 된다.
#include <iostream>
#include <queue>
using namespace std;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> q;
int n, m, ans, ar[301][301];
bool vis[301][301];
void bfs(int x, int y) {
vis[x][y] = true;
q.push({ x,y });
while (!q.empty()) {
auto cur = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (!vis[nx][ny] && !ar[nx][ny]) ar[cur.first][cur.second]--;
else if (!vis[nx][ny]) {
q.push({ nx,ny });
vis[nx][ny] = true;
}
}
if (ar[cur.first][cur.second] < 0)
ar[cur.first][cur.second] = 0;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> ar[i][j];
while (1) {
for (int i = 0; i < n; ++i) fill(vis[i], vis[i] + m, false);
int land = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (vis[i][j] || !ar[i][j]) continue;
bfs(i, j);
land++;
}
}
if (land > 1) break;
else if (land == 0) {
ans = 0; break;
}
ans++;
}
cout << ans << endl;
return 0;
}
'알고리즘 > BOJ' 카테고리의 다른 글
BOJ 1922 네트워크 연결 (0) | 2020.11.14 |
---|---|
BOJ 10282 해킹 (0) | 2020.11.11 |
BOJ 4485 녹색 옷 입은 애가 젤다지? (0) | 2020.11.06 |
BOJ 1238 파티 (0) | 2020.11.05 |
BOJ 9370 미확인 도착지 (0) | 2020.11.05 |