[백준] 단지번호 붙이기 문제 자바스크립트 풀이 - BFS

> 문제 바로가기

2667번: 단지번호붙이기

 

백준 맞왜틀 극한이다. 4시간 붙들고 있었음

 

1. 접근 방향

 

(1) 집이 표시된 그래프와, 내가 확인했음을 기록한 그래프가 필요하다. 초기화시켜준다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = +input.shift(); 

// 집이 있는지 기록된 그래프
input = input.map((arr) => arr.trim().split("").map(x => +x));

// 내가 방문해서 확인했는지 기록하는 그래프
const visited = [];
for (let i = 0; i < n; i++) {
    visited.push(new Array(n).fill(0));
}

 

(2) 집 위치가 기록된 그래프와 내가 방문했는지 기록한 그래프를 확인하면서, 이중for문으로 집은 있는데 내가 아직 방문 안 한 집을 BFS로 검사한다.

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        if (+visited[i][j] === 0 && +input[i][j] === 1) {
            BFS(i, j);
        }
    }
}

 

(3) BFS 함수를 만든다. queue.shift()의 좌표랑 맞닿은 상하좌우 위치 중, 범위 내의 집이 있는지 확인하고 있으면 queue에 push()해준다.

    while (queue.length) {
        const target = queue.shift();
        curX = target[0];
        curY = target[1];
        
        if (visited[curX][curY] === 0) {
            visited[curX][curY] = 1;
            houses++;
            
            // 상하좌우 좌표를 확인한다. 
            for (let i = 0; i < 4; i++) {
            
            	// 상하좌우 좌표가 유효하고, 그 좌표에 집이 있으면 큐에 넣어준다.
                if (rangeCheck(curX + nX[i], curY + nY[i]) && 
                    input[curX + nX[i]][curY + nY[i]] === 1) 
                {
                    queue.push([curX + nX[i], curY+ nY[i]]);
                }
            }
        }
    }

 

2. 전체 해답

 

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = +input.shift(); 
input = input.map((arr) => arr.trim().split("").map(x => +x));
const visited = [];
for (let i = 0; i < n; i++) {
    visited.push(new Array(n).fill(0));
}

const nX = [0, 0, 1, -1]; 
const nY = [1, -1, 0, 0];
let complexes = []; 
let houses = 0;

const rangeCheck = (x, y) => {
    if (x < 0 || x >= n || y < 0 || y >= n) return false;
    return true;
}

const BFS = (curX, curY) => {
    const queue = [];
    queue.push([curX, curY]);
    houses = 0;
    
    while (queue.length) {
        const target = queue.shift();
        curX = target[0];
        curY = target[1];
        
        if (visited[curX][curY] === 0) {
            visited[curX][curY] = 1;
            houses++;
            
            for (let i = 0; i < 4; i++) {
                if (rangeCheck(curX + nX[i], curY + nY[i]) && 
                    input[curX + nX[i]][curY + nY[i]] === 1) 
                {
                    queue.push([curX + nX[i], curY+ nY[i]]);
                }
            }
        }
    }
    complexes.push(houses); 
}


for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        if (+visited[i][j] === 0 && +input[i][j] === 1) {
            BFS(i, j);
        }
    }
}

complexes.sort((a, b) => a - b);
let answer = [complexes.length, ...complexes];
console.log(answer.join("\n"));