# 문제 설명
문제 링크 : https://www.acmicpc.net/problem/2573
아래 그림처럼 빙산의 높이가 NxM 이차원 배열에 주어진다.
빈 칸은 전부 빙산이 아니므로 0으로 주어진다.
빙산은 1년이 지날 때마다 빙산의 상하좌우에 인접한 곳에 0이 있다면 (빙산이 아닌 부분과 인접하면) 그 갯수만큼 녹는다.
이 때, 아래 그림은 한 덩어리로 되어 있는데 두 덩어리 이상으로 쪼개지기까지 걸리는 년수를 출력하면 된다.
만약 모든 빙산이 다 녹을 때까지 두 덩어리 이상이 되지 않으면 0을 출력한다.
# 문제 풀이
N, M, map에 주어진 입력을 받고, map[i][j] 값이 0보다 큰 빙산이면 큐에 저장하도록 한다 (빙산이 아예 주어지지 않으면 result는 자연스럽게 0 출력)
이중반복문이 시작되고, 현재 빙산인 부분의 좌표와 높이를 저장하는 cur_ice 벡터와 지금 시점에서 1년 후에도 빙산인 부분의 좌표와 높이를 저장하는 next_ice 벡터를 정의한다. (그런데 실질적으론 next_ice와 cur_ice에 저장하는건 같고 next_ice 기준으로 높이를 체크해서 다음 큐에 담을 걸 걸러내긴 한다. 이 부분은 리팩토링 해야할 듯)
빙산 좌표와 높이를 담은 큐에서 현재 빙산 근처에 0이 있는지 (map[xx][yy] == 0인지?)를 체크하고 만약 있다면 녹기 전의 초기 높이(init_height, 초기값은 top.height)를 하나씩 줄이고(--) next_ice 벡터에 빙산의 좌표와 새로 녹은 값이 반영된 높이를 저장한다.
cur_q 큐를 선언해서 현재 방문중인 빙산 좌표중에 아무거나 하나를 집어넣고, 큐를 돌려서 시작점에서 방문하지 않았었고, 인접해있는 빙산(!visit[xx][yy] && map[xx][yy] > 0)들만 cur_q에서 다시 방문하도록 해서 지금이 한 덩어리인지 아닌지 체크한다.
cur_q 돌리는게 끝나면 포문으로 visit[cur_ice[i].x][cur_ice[i].y] 중에 한 좌표라도 방문되지 않았는지 체크하고, 방문되지 않은 빙산이 있다면 무조건 두 덩어리 이상이므로 현재 시간을 결과값에 저장, istwo = true로 할당하고 반복문을 빠져나오게 한다.
두 덩어리 이상이 아니라면 map 이차원 배열에 녹은 빙산의 높이들을 반영하고 빙산의 높이가 다시 0보다 큰 좌표들만 큐에 넣어서 위의 과정을 반복하도록 한다.
// 2573. 빙산
#define _CRT_SECURE_NO_WARINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
struct iceberg {
int x;
int y;
int height;
};
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int N, M;
int map[301][301];
int visit[301][301];
int result;
int cur_time;
queue<iceberg> Q;
bool istwo = false;
int main() {
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> map[i][j];
if (map[i][j] > 0) {
Q.push({ i, j, map[i][j] });
}
}
}
while (!Q.empty()) {
vector<iceberg> cur_ice;
vector<iceberg> next_ice;
memset(visit, 0, sizeof(visit));
while (!Q.empty()) {
iceberg top = Q.front();
cur_ice.push_back(top);
int init_height = top.height;
Q.pop();
/* 녹이는 작업 진행 */
for (int i = 0; i < 4; i++) {
int xx = top.x + dx[i];
int yy = top.y + dy[i];
if (xx < 1 || yy < 1 || xx > N || yy > M) continue;
if (map[xx][yy] == 0) init_height--;
}
next_ice.push_back({ top.x, top.y, init_height });
}
/*cur_q로 두 덩어리인지 아닌지 확인 */
queue<iceberg> cur_q;
cur_q.push(cur_ice[0]);
while (!cur_q.empty()) {
iceberg top = cur_q.front();
cur_q.pop();
visit[top.x][top.y] = 1;
for (int i = 0; i < 4; i++) {
int xx = top.x + dx[i];
int yy = top.y + dy[i];
if (xx < 1 || yy < 1 || xx > N || yy > M) continue;
if (!visit[xx][yy] && map[xx][yy] > 0) {
visit[xx][yy] = 1;
cur_q.push({ xx, yy, 0 });
}
}
}
for (int i = 0; i < cur_ice.size(); i++) {
if (visit[cur_ice[i].x][cur_ice[i].y] == 0) {
result = cur_time; istwo = true; break;
}
}
if (istwo) break;
else {
for (int i = 0; i < next_ice.size(); i++) {
int xx = next_ice[i].x;
int yy = next_ice[i].y;
if (next_ice[i].height <= 0) map[xx][yy] = 0;
else map[xx][yy] = next_ice[i].height;
if (next_ice[i].height > 0) Q.push(next_ice[i]);
}
}
cur_time++;
}
cout << result << endl;
}# 개선점 및 보완할 점
처음에 문제 설계를 잘못해서 시행착오를 너무 많이 했다.
- 두 덩어리인지 아닌지 확인하는 알고리즘
처음에는 이중 반복문 내에서 녹이는 작업을 진행하면서 동시에 두 덩어리인지 아닌지 세려고 했다.
예를 들어서, cur_ice 벡터에 현재 높이가 0보다 큰 빙산이 있으니까 그 빙산을 큐를 돌면서 방문하면서 인접한 곳에 빙산이 있으면 visit 배열에 1 표시를 해서 방문할 수 있으면 빙산이 모두 하나로 연결되어 있고, 그렇지 않으면 빙산이 연결되지 않았다. 라고 생각했는데 여기엔 큰 결함이 있었다.
엄청 간단한 반례인데, 문제에선 최소 3x3이지만 예를 들어 6 4 0 8 9 이런 식으로 빙산이 주어진다고 하면 6 4에서도 서로를 방문할 수 있고, 8 9 빙산에서도 서로를 방문할 수 있어서 visit 배열을 확인해보면 1 1 0 1 1로 나오고 visit[i][j] == 0이 성립하는 빙산이 없어서 분명히 두 덩어리여도 구분하지 못했다.
그래서 정석대로 cur_q 큐를 추가해서 map[xx][yy]가 0보다 큰(녹지 않은 빙산), 그리고 방문하지 않은(visit[i][j] == 0) 지점만을 순회해서 빙산 중에(cur_ice에 저장된 좌표들은 모두 빙산의 좌표들이니까 이걸로 비교) visit[i][j] == 0인 좌표가 하나라도 있다면 두 덩어리인걸로 간주하고 반복문을 빠져나와서 result를 출력하도록 했다. - 빙산을 녹이는 알고리즘
여기서도 실수를 했었는데, 예를 들어 0 2 0 9 9 라고 빙산이 주어지면 다음 출력때 0 0 0 8 9 라고 되어야 하는데 0 2 0 8 9 라는 이상한 일이 벌어졌다.
그 이유는, 이번 턴에 빙산이 녹아서 있던 빙산이 녹았을 때 (딱 0 값이 되었을 때) next_ice 벡터에 넣질 않아서 height가 0값이 되면 map에 반영이 안 되었기 때문이었다. 그래서, 일단 next_ice 벡터에 넣을 때 height가 0보다 큰것만 넣지말고 일단 다 넣은 다음에 다음 큐에 넣을 때만 height가 0보다 큰 것만 들어가도록 걸러서 저장하도록 했다. - 결과를 출력하는 알고리즘
계속 31%에서 틀렸습니다 가 나와서 반례를 보다가 알게 된건데, 처음부터 두 덩이가 입력으로 주어지는 입력이 있다는걸 알게 됐다.
그래서 처음부터 두 덩이는 visit 이차원 배열에서 인식을 못하나? 라고 생각했는데 아주 인식이 잘 됐다.
황당해져서 문제가 무엇인가 봤더니 bool istwo를 안 쓰고 바깥 반복문 탈출 조건을 if(result > 0)으로 했더니 처음부터 두 덩이일때는 result == 0이어야 해서 탈출을 못하고 두 덩이를 다 녹이고나서야 반복문 탈출이 되어서 엉뚱한 값이 나왔음을 알게 됐다.
그래서 bool istwo를 도입해서 result 값에 상관없이 두 덩이면 반복문을 모두 탈출할 수 있게 설계했다.
황당한 실수를 많이 했던 문제였지만, 대강 1년전의 내가 한 번 도전해서 '실패'만 띄워놓고 못 풀었던 문제를 1시간만에 풀어낸 것에 의의를 둬야겠다.
다음엔 같은 실수를 하지 않도록 주의하자.
