[Baekjoon] 빙산
👀 문제 설명
지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.
그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보
빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.
그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.
한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
입력
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
출력
첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.
예제 입력 1
5 7
0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0
0 7 6 2 4 0 0
0 0 0 0 0 0 0
예제 출력 1
2
✍🏻풀이
[틀림] - 왜 틀린지 모르겠음..
Stack을 사용한 DFS를 활용해 빙산의 개수가 몇 개인지 구하고, 빙산의 개수가 2개 이상이면 year를 출력하고 0개이면 0을 출력한다. (다 녹을 때까지 2개 이상이 안되면 0을 출력행야 하므로)
그리고 빙산의 개수가 1개라면 year을 +1 하고, 빙산을 녹이면 된다.
빙산을 녹일 때 주의할 점은, 녹인 빙산을 바로 iceberg에 저장하면 오류가 날 수 있기 때문에 녹인 빙산을 새로운 배열에 저장해두고, 다 녹인 후에 빙산 값을 바꿔야 한다는 점이다.
이유)
0 0 0 0 0 0
0 0 2 5 0 0
0 0 0 0 0 0
녹이기 전 빙산이 위와 같을 경우, 녹인 값을 바로 저장하면 2 -> 0으로 바뀌기 때문에 5 위치가 1이 된다. (올바른 값은 2)
-> 근데 틀림
[정답]
BFS를 사용해서 풀었다. (푸는 방법은 위와 같음)
코드
틀린 답
// 빙산 (https://www.acmicpc.net/problem/2573)
#include <iostream>
#include <stack>
#include <cstring>
#define MAX 300
using namespace std;
int N, M;
int iceberg[MAX][MAX];
int visited[MAX][MAX];
int dx[4] = { 1, 0, -1, 0};
int dy[4] = { 0, 1, 0, -1 };
/**
* 1. DFS를 사용해서 빙산이 몇 덩어리인지 확인한다.
* 2-1. 2덩어리 미만이면 year + 1 하고, 1년 후 녹은 빙산의 현황을 저장한다.
* 2-2. 2덩어리 이상이면 year를 출력하고 return
* 다 녹을때까지 반복
*/
void melt() {
int newIceberg[MAX][MAX];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (iceberg[i][j] == 0) // 빙산이 없다면 continue
continue;
// (i, j) 위치에는 빙산이 있다.
int adj = 0; // 바닷물이 얼마나 인접해있는지 저장하는 변수
for (int dir = 0; dir < 4; dir++) {
int nextX = i + dx[dir];
int nextY = j + dy[dir];
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M || iceberg[nextX][nextY] != 0) // 범위를 벗어났거나, 인접한 곳이 빙산이라면 continue
continue;
adj++;
}
if (iceberg[i][j] - adj <= 0) {
newIceberg[i][j] = 0;
}
else {
newIceberg[i][j] = iceberg[i][j] - adj;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
iceberg[i][j] = newIceberg[i][j];
}
}
}
// DFS 사용
int getIcebergNum() {
int answer = 0;
memset(visited, 0, sizeof(visited)); // visited 배열 0으로 초기화
stack<pair<int, int>> S;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (visited[i][j] == 0 && iceberg[i][j] != 0) {
S.push({ i, j });
visited[i][j] = 1;
// DFS
while (!S.empty()) {
int curX = S.top().first;
int curY = S.top().second;
S.pop();
for (int dir = 0; dir < 4; dir++) {
int nextX = curX + dx[dir];
int nextY = curY + dy[dir];
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M || visited[nextX][nextY] != 0) // 범위를 벗어나거나 이미 방문한 곳이라면 continue
continue;
if (iceberg[nextX][nextY] != 0) { // 아직 방문하지 않았고, 빙산이 있는 위치라면
S.push({ curX, curY });
S.push({ nextX, nextY });
visited[nextX][nextY] = 1;
break;
}
}
}
answer++;
}
}
}
return answer;
}
bool isAllIceberg() {
bool ans = true;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (iceberg[i][j] == 0) {
return false;
}
}
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
// input
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> iceberg[i][j];
}
}
// solve
int year = 0;
while (true) {
if (isAllIceberg()) {
cout << "0\n";
break;
}
int curIceberg = getIcebergNum();
if (curIceberg >= 2) { // 빙산이 두 덩어리 이상으로 분리되었으면
cout << year << "\n"; // year를 출력하고 break
break;
}
else if (curIceberg == 0) { // 빙산이 다 녹았을 경우
cout << "0\n"; // year를 출력하고 break
break;
}
// 빙산이 한 덩어리고 아직 다 안녹았을 경우
year++;
melt();
}
return 0;
}
정답
// 빙산 (https://www.acmicpc.net/problem/2573)
#include <iostream>
#include <queue>
#include <cstring>
#define MAX 300
using namespace std;
int N, M;
int iceberg[MAX][MAX];
int copyIceberg[MAX][MAX];
int visited[MAX][MAX];
int dx[4] = { 1, 0, -1, 0};
int dy[4] = { 0, 1, 0, -1 };
/**
* 1. BFS를 사용해서 빙산이 몇 덩어리인지 확인한다.
* 2-1. 2덩어리 미만이면 year + 1 하고, 1년 후 녹은 빙산의 현황을 저장한다.
* 2-2. 2덩어리 이상이면 year를 출력하고 return
* 다 녹을때까지 반복
*/
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> iceberg[i][j];
}
}
}
void BFS(int a, int b) {
queue<pair<int, int>> Q;
Q.push({ a, b });
visited[a][b] = 1;
while (!Q.empty()) {
int curX = Q.front().first;
int curY = Q.front().second;
Q.pop();
for (int dir = 0; dir < 4; dir++) {
int nextX = curX + dx[dir];
int nextY = curY + dy[dir];
if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M)
continue;
if (visited[nextX][nextY] == 0 && iceberg[nextX][nextY] != 0) {
visited[nextX][nextY] = 1;
Q.push({ nextX, nextY });
}
}
}
}
// (x, y)에 바다가 얼마나 붙어있는지 값 return
int melt(int x, int y) {
int count = 0;
for (int dir = 0; dir < 4; dir++) {
int nextX = x + dx[dir];
int nextY = y + dy[dir];
if (iceberg[nextX][nextY] == 0)
count++;
}
return count;
}
void solution() {
int year = 0;
while (true) {
int land_count = 0;
memset(visited, 0, sizeof(visited)); // visited 초기화
memset(copyIceberg, 0,sizeof(copyIceberg)); // copyIceberg 초기화 (녹인 후의 배열을 저장하기 위해)
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (iceberg[i][j] != 0 && visited[i][j] == 0) {
land_count++;
BFS(i, j);
}
}
}
if (land_count >= 2) {
cout << year << "\n";
break;
}
if (land_count == 0) {
cout << 0 << "\n";
break;
}
// 빙산 녹이기
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (iceberg[i][j] != 0) {
copyIceberg[i][j] = iceberg[i][j] - melt(i, j);
if (copyIceberg[i][j] < 0)
copyIceberg[i][j] = 0;
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
iceberg[i][j] = copyIceberg[i][j];
}
}
year++;
}
}
void solve() {
input();
solution();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
solve();
return 0;
}