반응형
https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지
www.acmicpc.net
녹고, 지역 나누고
따로 수행하기!
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int n, m;
int map[301][301];
int temp[301][301];
int visited[301][301];
int year;
int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };
int areaCount;
int qcount;
int flag;
queue<pair<int, pair<int, int>>> q;
void copyMap() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
map[i][j] = temp[i][j];
}
}
qcount = q.size();
}
void melting() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cnt = 0;
if (map[i][j] > 0) {
for (int d = 0; d < 4; d++) {
if (map[i + dx[d]][j + dy[d]] == 0) {
cnt++;
}
}
temp[i][j] = map[i][j] - cnt;
if (temp[i][j] < 0) temp[i][j] = 0;
}
}
}
copyMap();
}
void divideArea() {
while (!q.empty()) {
int val = q.front().first;
int cx = q.front().second.first;
int cy = q.front().second.second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (map[nx][ny] != 0 && visited[nx][ny] == 0 && nx >= 0 && ny >= 0 && nx < n && ny < m) {
visited[nx][ny] = 1;
q.push(make_pair(val+1, make_pair(nx, ny)));
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &map[i][j]);
}
}
year = 0;
while (-1) {
while (!q.empty()) q.pop();
memset(visited, 0, sizeof(visited));
memset(temp, 0, sizeof(temp));
areaCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == 0 && map[i][j] != 0) {
areaCount++;
if (areaCount >= 2) break;
q.push(make_pair(areaCount, make_pair(i, j)));
divideArea();
}
}
}
if (areaCount >= 2) break;
if (areaCount == 0) break;
melting();
year++;
}
if (areaCount == 0) {
printf("%d", 0);
}else {
printf("%d", year);
}
}
반응형