반응형
▷ 문제 : 2573번 - 빙산
▷ 해결 날짜 : 2022.07.26
▷ 소요 시간 : 1시간 30분
▷ 풀이 과정 :
문제를 요약하자면 지구 온난화로 빙산이 녹는데 빙산이 최초로 두 덩어리로 분리되는 데 걸리는 시간(년)을 구하는 문제이다.
문제가 얼핏보면 쉬워 보이지만, 몇 개 중요하게 체크하고 가야 할 점과 구현할 때 주의해야 할 점이 있다.
- 1년식 증가하며 매년 빙산이 녹는데, 각 빙산의 높이는 동서남북 방향으로 붙어있는 0이 저장된 칸의 개수만 큼 줄어든다. (예를 들어 해당 위치의 값이 5이며 상하좌우의 0으로된 칸이 3개 있으면 여기는 내년에 2가 된다.)
- 구현 시 빙산의 덩어리 개수를 구한 뒤 다음 해로 넘어갈때 모든 빙산의 높이를 "동시에" 녹여줘야 한다. (아래 구현 코드를 보면 각 얼음덩어리를 녹이면서 0대신에 -1로 적용하고 그다음에 -1을 전부 0으로 변경해주는 것을 볼 수 있다.)
- 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다. (그래서 이중배열을 돌릴 때 1부터 시작해서 n/m -1까지 돌리는 것이다.)
얼추 이정도만 숙지하고 있다면 크게 어려움을 없을 텐데, 문제를 풀면서 시간을 많이 쏟은 부분은 바로 "시간 초과"이다.
방문(visited) 처리하는 부분에서 동서남북 체크할때 그때그때 방문 처리해주는 것으로 시간 초과를 통과 하였다.
(원래는 while문 시작 부분에서 방문처리했었는데, 계속 시간 초과가 발생하였다.)
▷ 구현
let fs = require("fs");
let input = fs.readFileSync("./dev/stdin").toString().split("\n");
const ds = [
[-1, 0],
[1, 0],
[0, 1],
[0, -1],
];
const [N, M] = input.shift().split(" ").map(Number);
let iceberg = input.map((v) => v.split(" ").map(Number));
const meltIceFromNextYear = () => {
iceberg.forEach((ice, x) => {
ice.forEach((height, y) => {
if (height > 0) {
let count = 0;
for (let i = 0; i < 4; i++) {
const xPos = x + ds[i][0];
const yPos = y + ds[i][1];
if (iceberg[xPos][yPos] === 0) count++;
}
const nextHeight = iceberg[x][y] - count;
iceberg[x][y] = nextHeight <= 0 ? -1 : nextHeight;
}
});
});
};
const changeMinusToZero = () => {
iceberg.forEach((ice, x) => {
ice.forEach((height, y) => {
if (height === -1) iceberg[x][y] = 0;
});
});
};
const bfs = (startX, startY, visited) => {
const queue = [[startX, startY]];
while (queue.length) {
const [x, y] = queue.shift();
for (let i = 0; i < 4; i++) {
const xPos = x + ds[i][0];
const yPos = y + ds[i][1];
if (xPos < 0 || yPos < 0 || xPos >= N || yPos >= M) continue;
if (iceberg[xPos][yPos] > 0 && !visited[xPos][yPos]) {
visited[xPos][yPos] = 1;
queue.push([xPos, yPos]);
}
}
}
};
let year = 0;
while (true) {
const visited = Array.from(Array(N), () => Array(M).fill(0));
let lump = 0;
for (let i = 1; i < N - 1; i++) {
for (let j = 1; j < M - 1; j++) {
if (iceberg[i][j] > 0 && !visited[i][j]) {
visited[i][j] = 1;
bfs(i, j, visited);
lump++;
}
}
}
if (lump >= 2) {
console.log(year);
break;
} else if (lump === 0) {
console.log(0);
break;
}
year++;
meltIceFromNextYear();
changeMinusToZero();
}
▷ 복기 :
지금까지 풀었던 문제 유형과 비슷해 보여서 처음에는 좀 쉽게 접근했었는데, 생각해서 구현해야 하는 부분들이 좀 있어서 피곤한 문제였다...
반응형
댓글