[JavaScript/DFS] 백준 실버 1 : 2583 - 영역 구하기

 

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

2583번: 영역 구하기

---

📌 작성한 코드 

// 2583
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 [M, N, K] = input.shift().split(" ").map(Number);
const map = Array.from({ length: N }, () => new Array(M).fill(false));

for (let i = 0; i < K; i++) {
    const [x1, y1, x2, y2] = input.shift().split(" ").map(Number);
    for (let j = x1; j < x2; j++) {
        for (let k = y1; k < y2; k++) {
            map[j][k] = true;
        }
    }
}

const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];

const dfs = (a, b) => {
    let count = 0;
    const stack = [];
    stack.push([a, b]);
    map[a][b] = true;

    while (stack.length) {
        const [x, y] = stack.pop();
        count++;
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (!map[nx][ny]) {
                stack.push([nx, ny]);
                map[nx][ny] = true;
            }
        }
    }
    return count;
};

const answer = [];

for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
        if (!map[i][j]) {
            answer.push(dfs(i, j));
        }
    }
}

console.log(answer.length);
console.log(answer.sort((a, b) => a - b).join(" "));

 

📌 풀이 

블럭의 범위를 방문처리 해준 뒤 방문하지 않은 부분에 대해서 dfs를 돌며 영역의 범위를 구하면 되는 문제이다.

 

1. 영역의 시작, 끝 좌표를 입력받고 해당 범위만큼 방문처리 해준다.

for (let i = 0; i < K; i++) {
    const [x1, y1, x2, y2] = input.shift().split(" ").map(Number);
    for (let j = x1; j < x2; j++) {
        for (let k = y1; k < y2; k++) {
            map[j][k] = true;
        }
    }
}

2. dfs를 통해 방문하지 않은 영역 방문하고, 영역의 개수를 세어준다. 

const dfs = (a, b) => {
    let count = 0;
    const stack = [];
    stack.push([a, b]);
    map[a][b] = true;

    while (stack.length) {
        const [x, y] = stack.pop();
        count++; // stack에서 꺼내면서 블럭의 개수 증가시키기
        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (!map[nx][ny]) {
                stack.push([nx, ny]);
                map[nx][ny] = true;
            }
        }
    }
    return count; // 블럭의 개수 반환
};

3. 전체 영역을 반복문을 돌면서 방문되지 않은 위치에서 dfs 돌면서 영역의 개수와 범위를 구해준다.

const answer = [];

for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
        if (!map[i][j]) {
            answer.push(dfs(i, j));
        }
    }
}

console.log(answer.length);
console.log(answer.sort((a, b) => a - b).join(" "));

 

✅ 성공