[JavaScript/BFS] 백준 실버 1 : 2667 - 단지번호붙이기

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

2667번: 단지번호붙이기

---

📌  작성한 코드 

// 2667

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());
const arr = input.map((row) => row.split("").map(Number));

const solution = () => {
    const answer = [];
    const dx = [1, -1, 0, 0];
    const dy = [0, 0, 1, -1];

    const bfs = (a, b) => {
        let count = 1;
        const queue = [[a, b]];
        arr[a][b] = 2;

        while (queue.length) {
            const [x, y] = queue.shift();
            for (let i = 0; i < 4; i++) {
                const nx = x + dx[i];
                const ny = y + dy[i];
                if (nx >= N || ny >= N || nx < 0 || ny < 0) continue;
                if (arr[nx][ny] === 1) {
                    queue.push([nx, ny]);
                    arr[nx][ny] = 2;
                    count++;
                }
            }
        }
        return count;
    };

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (arr[i][j] === 1) {
                answer.push(bfs(i, j));
            }
        }
    }
    answer.sort((a, b) => a - b);
    console.log(answer.length);
    for (const home of answer) {
        console.log(home);
    }
};
solution();

 

📌 풀이 

1. BFS

- 입력받은 시작노드에서부터 집이 있는(배열 내에서 1인)곳을 탐색한다.

- 해당 집을 탐색한 후에는 방문처리를 하고(2로 변경), 해당 값을 큐에 삽입한다(해당 집의 상하좌우를 또 탐색하기 위해) 

- 해당 집을 탐색한 후에는 마찬가지로 집의 개수를 세기 위해서 count 값을 증가시킨다

const bfs = (a, b) => {
        let count = 1; // 시작노드는 집이 있다는 의미이기 때문에 1로 시작
        const queue = [[a, b]];
        arr[a][b] = 2; // 시작노드 방문처리

        while (queue.length) {
            const [x, y] = queue.shift(); 
            for (let i = 0; i < 4; i++) { // 상하좌우 확인
                const nx = x + dx[i];
                const ny = y + dy[i];
                if (nx >= N || ny >= N || nx < 0 || ny < 0) continue; // 범위 벗어나면 확인안함
                if (arr[nx][ny] === 1) { // 방문하지 않은 집이면 방문하고 방문처리
                    queue.push([nx, ny]); 
                    arr[nx][ny] = 2; 
                    count++;
                }
            }
        }
        return count;
    };

 

2. 반복 

- 배열의 모든 위치에서 방문하지 않은 집이라면 bfs 적용한다.

- bfs에서 방문하면 방문처리를 통해 값이 1이 아닌 다른 값으로 변경되므로 이미 확인한 단지를 다시 확인하는 경우 발생하지 x 

for (let i = 0; i < N; i++) {
        for (let j = 0; j < N; j++) {
            if (arr[i][j] === 1) {
                answer.push(bfs(i, j));
            }
        }
    }

 

3. 정답 출력 

- 확인한 집 수를 정렬해서, 단지의 수와 각 단지에 포함된 집의 수를 오름차순으로 출력한다.

answer.sort((a, b) => a - b);
    console.log(answer.length);
    for (const home of answer) {
        console.log(home);
    }

 

---