[JavaScript/DFS] 백준 실버 1 : 2468번 - 안전 영역

 

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

---

📌 작성한 코드 

// 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);

 

 

📌 사담

- 디버깅 한번도 하지 않고, 단번에 맞춰서 기분이 너무 좋은 문제!

---