https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
📌 작성한 코드
// 2468
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = parseInt(input.shift(), 10);
let max = 0;
let min = Infinity;
const arr = input.map((i) => {
const temp = i.split(" ").map(Number);
const tempMax = Math.max(...temp);
const tempMin = Math.min(...temp);
if (max < tempMax) max = tempMax;
if (min > tempMin) min = tempMin;
return temp;
});
const solution = () => {
const answer = [];
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const dfs = (x, y, index, visited) => {
const stack = [[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 && nx < N) {
if (arr[nx][ny] >= index && !visited[nx][ny]) {
visited[nx][ny] = true;
stack.push([nx, ny]);
}
}
}
}
};
for (let i = min; i <= max; i++) {
const visited = Array.from(Array(N), () => new Array(N).fill(false));
let count = 0;
for (let j = 0; j < N; j++) {
for (let k = 0; k < N; k++) {
if (arr[j][k] >= i && !visited[j][k]) {
dfs(j, k, i, visited);
count++;
}
}
}
answer.push(count);
}
return Math.max(...answer);
};
console.log(solution());
📌 풀이
✅ 1. 입력 받기
- 입력받으면서 문자열을 숫자의 배열로 바꾸는 과정에서 해당 배열이 가진 최댓값과 최솟값을 같이 구해준다
- 각 높이에 대한 반복문을 돌 때 최솟값부터 최댓값까지 도는 것이 더 효율적이기 때문이다.
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = parseInt(input.shift(), 10);
let max = 0;
let min = Infinity;
const arr = input.map((i) => {
const temp = i.split(" ").map(Number);
const tempMax = Math.max(...temp);
const tempMin = Math.min(...temp);
if (max < tempMax) max = tempMax;
if (min > tempMin) min = tempMin;
return temp;
});
✅ 2. 반복문 작성
- 비의 양에 따른 모든 경우의 수를 고려하면서 안전 영역을 확인해야 하기 때문에 비의 양이 높이의 최솟값부터 최댓값일때까지를 모두 검사한다.
-> 최솟값 미만이면 하나도 잠기지 않고, 최댓값 초과면 모두가 잠겨버리기 때문에 안전영역을 구할 필요가 없음
- 비의 양이 i 일 때, dfs를 통해 안전 영역을 찾을 것이다.
- 이중 루프를 사용해서 아직 방문하지 않고, 비의 양인 i 이상의 높이를 가진 곳의 영역에서 부터 시작해서 안전 영역의 크기를 구한다.
- dfs가 끝나면, 해당 지점과 연결된 안전 영역을 구했기 때문에, 안전영역의 개수인 count를 ++ 해준다.
- i 높이에 대한 안전영역의 개수를 모두 세주었으면 answer에 개수를 추가해준다.
for (let i = min; i <= max; i++) {
const visited = Array.from(Array(N), () => new Array(N).fill(false));
let count = 0;
for (let j = 0; j < N; j++) {
for (let k = 0; k < N; k++) {
if (arr[j][k] >= i && !visited[j][k]) {
dfs(j, k, i, visited);
count++;
}
}
}
answer.push(count);
}
✅ 3. dfs 작성
- stack에 시작 지점을 추가하고, 방문 여부를 기록한 다음에 반복문을 시작한다.
- stack에 아이템이 있는 동안 반복할 것이다.
- stack에서 방문한 좌표를 꺼내고, 상하좌우로 이동한 위치를 구한다(nx, ny)
- 이동한 위치가 배열의 범위를 초과하지 않고, 높이가 index(i)보다 크거나 같으며 방문한 적이 없으면 stack에 추가하고 방문해준다.
-> 이렇게 모든 지점을 방문해주면 시작 지점과 연결된 모든 안전 영역 범위를 방문하게 된다.
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
const dfs = (x, y, index, visited) => {
const stack = [[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 && nx < N) {
if (arr[nx][ny] >= index && !visited[nx][ny]) {
visited[nx][ny] = true;
stack.push([nx, ny]);
}
}
}
}
};
✅ 4. 답 출력
- 모은 안전영역의 개수들 중에서 가장 큰 값을 답으로 출력한다.
return Math.max(...answer);
📌 사담
- 디버깅 한번도 하지 않고, 단번에 맞춰서 기분이 너무 좋은 문제!

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/BFS] 백준 실버 1 : 1926번 - 그림 (0) | 2023.10.10 |
|---|---|
| [JavaScript/DFS] 백준 골드 4 : 2573번 - 빙산 (0) | 2023.09.22 |
| [JavaScript/BFS] 백준 실버 1 : 1697 - 숨바꼭질 (0) | 2023.09.19 |
| [JavaScript/BFS] 백준 골드 5 : 7569 - 토마토 (0) | 2023.09.18 |
| [JavaScript/BFS] 백준 실버 2 : 2644 - 촌수계산 (0) | 2023.09.14 |