https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
📌 작성한 코드
// 2573
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M] = input.shift().split(" ").map(Number);
let iceberg = input.map((i) => i.split(" ").map(Number));
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const meltIce = (temp) => {
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (iceberg[i][j] > 0) {
let count = 0;
for (let k = 0; k < 4; k++) {
const nx = i + dx[k];
const ny = j + dy[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
if (iceberg[nx][ny] === 0) {
count++;
}
}
}
if (temp[i][j] < count) temp[i][j] = 0;
else temp[i][j] -= count;
}
}
}
return temp;
};
const dfs = (x, y, temp, visited) => {
const stack = [];
stack.push([x, y]);
visited[x][y] = true;
while (stack.length) {
const [a, b] = stack.pop();
for (let i = 0; i < 4; i++) {
const nx = a + dx[i];
const ny = b + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
if (temp[nx][ny] > 0 && !visited[nx][ny]) {
stack.push([nx, ny]);
visited[nx][ny] = true;
}
}
}
}
};
const countIceberg = (temp) => {
let ice = 0;
const visited = Array.from(new Array(N), () => new Array(M).fill(false));
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (temp[i][j] > 0 && !visited[i][j]) {
dfs(i, j, temp, visited);
ice++;
}
}
}
return ice;
};
const solution = () => {
if (countIceberg(iceberg) >= 2) return 0;
let answer = 1;
while (true) {
const tempArr = iceberg.map((v) => [...v]);
const changed = meltIce(tempArr);
const count = countIceberg(changed);
if (count >= 2) return answer;
if (count === 0) return 0;
iceberg = changed.map((v) => [...v]);
answer++;
}
};
console.log(solution());
📌 풀이
✅ 1. 빙산 녹이기
- 바다(0)와 맞닿아있는 부분의 개수만큼 빙산을 녹이는 함수
- 반복문을 돌면서 해당 위치에 빙하가 있다면 상하좌우를 확인해서 바다와 맞닿은만큼 녹여준다.
- 주의!
-> 원본 iceberg를 바로 녹이고 다른 부분의 빙하를 녹이게 되면, 앞서 녹인 빙하 때문에 다른 부분의 빙하를 녹이는 과정에서 바다와 맞닿아있는 부분의 수가 증가될 수 있음
-> 그래서 맞닿아있는 부분의 수는 원본인 iceberg를 보고 확인하고, 실제 녹이는 것은 입력으로 들어온 temp 배열을 녹인다
- 빙하는 0보다 더 녹을 수 없기 때문에 맞닿은 바다의 수가 현재 빙하의 높이보다 크다면 0으로 설정해주고, 아니면 수만큼 빙하를 녹인다.
const meltIce = (temp) => {
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (iceberg[i][j] > 0) {
let count = 0;
for (let k = 0; k < 4; k++) {
const nx = i + dx[k];
const ny = j + dy[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
if (iceberg[nx][ny] === 0) {
count++;
}
}
}
if (temp[i][j] < count) temp[i][j] = 0;
else temp[i][j] -= count;
}
}
}
return temp;
};
✅ 2. dfs 사용해서 빙산 구하기
- 각 빙하가 이어져있는 빙산 한개를 구하는 함수
- 상하좌우를 확인해서 범위 내에 있고, 방문한 적이 없으면 stack에 넣고 방문하는 방식으로 빙산 한개의 범위를 다 확인한다.
const dfs = (x, y, temp, visited) => {
const stack = [];
stack.push([x, y]);
visited[x][y] = true;
while (stack.length) {
const [a, b] = stack.pop();
for (let i = 0; i < 4; i++) {
const nx = a + dx[i];
const ny = b + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
if (temp[nx][ny] > 0 && !visited[nx][ny]) {
stack.push([nx, ny]);
visited[nx][ny] = true;
}
}
}
}
};
✅ 3. 빙산의 수를 구하기
- 반복문을 돌면서 빙산을 구하는 함수
- 각 위치에 방문한 적이 없고(다른 빙산에 카운트 된 곳이 아니고), 0보다 크면(바다가 아니면) 해당 위치에서 dfs로 빙산을 구한다.
- dfs가 한번 끝나면 연결된 빙산 하나를 구한 것이므로 ice의 카운트를 세서 빙산의 개수를 세준다.
const countIceberg = (temp) => {
let ice = 0;
const visited = Array.from(new Array(N), () => new Array(M).fill(false));
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
if (temp[i][j] > 0 && !visited[i][j]) {
dfs(i, j, temp, visited);
ice++;
}
}
}
return ice;
};
✅ 4. 몇년이 지났는지 확인하기
- 처음부터 빙산이 2개 이상으로 나뉘어져 있다면, 0을 반환(0년이 걸렸으니까)
- iceberg를 바로 녹여버리면 다른 빙하에 맞닿는 빙하의 수에 영향이 갈 수 있으니까 복사해서 사용한다.
- 복사한 빙하 배열을 meltIce()로 녹여준다.
- 녹이고 난 다음의 빙하 배열을 countIceberg()로 빙산의 개수를 세준다
-> 해당 빙산이 2개 이상이면 현재 년수(answer)를 출력해준다.
-> 빙하가 모두 녹아버려서 빙산이 0개라면 0을 반환해준다.(두개로 나뉘지 않음)
-> 그리고 원본 배열을 녹은 빙하 배열로 업데이트 해서 다음 반복때는 녹은 빙하 배열을 사용할 수 있게 한다.
const solution = () => {
if (countIceberg(iceberg) >= 2) return 0;
let answer = 1;
while (true) {
const tempArr = iceberg.map((v) => [...v]);
const changed = meltIce(tempArr);
const count = countIceberg(changed);
if (count >= 2) return answer;
if (count === 0) return 0;
iceberg = changed.map((v) => [...v]);
answer++;
}
};
❗️ 주의
- 처음부터 빙산이 2개 이상인 경우 0을 출력하는 부분 써주기
if (countIceberg(iceberg) >= 2) return 0;
- 모든 빙하가 녹을 때까지 반복문 돌리기
-> 바다와 전혀 맞닿지 않은 빙하가 있다면 반복문을 많이 돌려야 녹는 경우가 있으므로, for문과 같이 제한을 두고 반복문을 돌리지말고 while을 사용해서 모든 빙하가 녹을 때까지 반복해주고, 0을 반환해준다.
while (true) {
// ...
if (count === 0) return 0;
// ...
}
- 복사해서 빙하 녹이기
-> 원본 배열을 녹이면 같은 라운드에 다른 빙하를 녹이는데 영향을 미침
-> 다 사용하고 다시 업데이트 해주기
const tempArr = iceberg.map((v) => [...v]);
const changed = meltIce(tempArr);
const count = countIceberg(changed);
iceberg = changed.map((v) => [...v]);
📌 사담
- 주의사항에 쓴 부분때문에 생각보다 오래걸렸던 문제
- 한 단계마다 디버깅 하는 습관을 까먹지 않게 주의하자!
- 이제 dfs/bfs 문제가 좀 재밌다. 풀면서 재밌었다.

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DFS] 백준 실버 2 : 1012 - 유기농 배추 (0) | 2024.01.08 |
|---|---|
| [JavaScript/BFS] 백준 실버 1 : 1926번 - 그림 (0) | 2023.10.10 |
| [JavaScript/DFS] 백준 실버 1 : 2468번 - 안전 영역 (0) | 2023.09.21 |
| [JavaScript/BFS] 백준 실버 1 : 1697 - 숨바꼭질 (0) | 2023.09.19 |
| [JavaScript/BFS] 백준 골드 5 : 7569 - 토마토 (0) | 2023.09.18 |