[JavaScript] 구름톤 챌린지 3주차 코딩테스트 : 발전기

📌  문제

📌  입력

📌  출력 및 예제

---

📌  풀이

알아야 하는 것

• Array.from

구할 것

• 전력을 공급할 수 있는 조건은 1인 칸에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받으면 된다.
  • 따라서 먼저 마을을 탐색하면서 1이면서 방문하지 않은 곳을 찾는다.
  • 이 곳에 발전기를 설치하고, 방문처리를 한 후 이 곳을 중점으로 상하좌우를 찾는다.
  • 해당 점을 curX, curY로 시작해서 상하좌우를 범위에 맞게 확인하고, 1이면서 방문하지 않은 곳인지를 체크해 다시 queue에 넣어준다. 넣음과 동시에 방문 처리도 해주어야 한다.
  • 방금 넣은 nextX, nextY를 기준으로 다시 처음처럼 도는데, 만약 넣은 nextX, nextY가 없다면 처음 시작한 이중 for문이 증가하면서 다른 쪽을 탐색하고, 그 곳을 시작으로 돌게 된다.
• 코드를 짜는 건 어렵지 않았는데 electronic을 어디에 추가해야 하는지 잘 감이 안와서 이 부분을 좀 헤맸다... 언제쯤 후루룩 풀까?

const readline = require('readline');
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
let input = [];
rl.on('line', (line) => {
    input.push(line);
    if (input.length === Number(input[0]) + 1) {
        rl.close();
    }
});

rl.on('close', () => {
    let scale = Number(input.shift());
    let map = input.map((v) => v.split(" ").map(v => Number(v)));
    let visited = Array.from(Array(scale), () => Array(scale).fill(false));
    let electronic = 0;

    let dt = [[0, -1], [0, 1], [-1, 0], [1, 0]];

    for (let i = 0; i < scale; i++) {
        for (let j = 0; j < scale; j++) {
            if (map[i][j] === 1 && !visited[i][j]) {
                electronic += 1;
                visited[i][j] = true;
                let queue = [[i, j]];


                while (queue.length) {
                    let [curX, curY] = queue.shift();

                    for (let k = 0; k < 4; k++) {
                        let nextX = curX + dt[k][0];
                        let nextY = curY + dt[k][1];

                        if (nextX >= 0 && nextX < scale && nextY >= 0 && nextY < scale && map[nextX][nextY] === 1 && !visited[nextX][nextY]) {
                            queue.push([nextX, nextY]);
                            visited[nextX][nextY] = true;
                        }
                    }
                }
            }
        }
    }

    console.log(electronic);
});