2667 단지번호붙이기

알고리즘: BFS

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

const n = +input.shift(); // 1
const map = input.map((v) => v.split('').map(Number)); // 2
const visited = []; // 4
const answer = []; // 3

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

// 4
for (var i = 0; i < n; i++) {
  visited.push([]);
  for (var j = 0; j < n; j++) {
    visited[i][j] = 0;
  }
}

n - 지도의 크기를 number 타입으로 나타낸다.
map - 주어진 지도를 이차원 배열로 구성한다.
1. 집이 없다면 0, 있다면 1
answer - 각 단지별 세대 수(노드)를 담을 배열을 나타낸다.
visited - 지도와 같은 사이즈의 이차원 배열을 구성하고, 0으로 채운다.
1. 방문하지 않은 노드라면 0, 방문한 노드라면 1
dx 와 dy - 방문중인 노드의 상하좌우를 탐색하기 위한 탐색용 배열

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (!visited[i][j] && map[i][j]) {
      bfs(i, j);
    }
  }
}

이차원으로 구성된 각 노드를 방문하기 위해 이중 반복문을 사용한다. 이때 방문하지 않은 노드이면서 집이 존재하는 노드일 때만 **넓이 우선 탐색(BFS)**을 를 실행한다.

BFS

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

// ...

function bfs(x, y) {
  let count = 1; // 탐색을 시작했으므로 초기값 1로 카운트 시작
  const queue = [x, y]; // 시작 노드

  visited[x][y] = 1; // 방문 처리

  while (queue.length) {
    // queue의 길이만큼 반복
    let x = queue.shift(); // queue 에서 x값을 꺼냄
    let y = queue.shift(); // queue에서 y값을 꺼냄

    for (let i = 0; i < 4; i++) {
      // 상하좌우 총 4번의 탐색을 위해 반복
      let nx = x + dx[i]; // 현재 탐색중인 노드를 기준으로 상하좌우 x좌표
      let ny = y + dy[i]; // 현재 탐색중인 노드를 기준으로 상하좌우 y좌표
      if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
        // 지도를 벗어나지 않는 범위
        if (!visited[nx][ny] && map[nx][ny]) {
          // 방문하지 않았으며 집이 존재한다면
          queue.push(nx, ny); // queue에서 다음 노드 대기
          visited[nx][ny] = 1; // 다음 노드 방문 처리
          count++; // 단지 내 세대 수 카운트 + 1
        }
      }
    }
  }
  answer.push(count); // answer 배열에 단지 내 세대 수를 push
}

Output

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

각 단지를 순회할 때마다 단지 내 세대 수를 push 했으므로 단지 수는 answer 배열의 길이가 되고, 각 단지별 세대 수는 오름차순으로 정렬하여 join 메소드로 줄내림하여 출력했다.

Full Code

const input = require('fs').readFileSync('./input.txt').toString().trim().split('\n');

const n = +input.shift();
const map = input.map((v) => v.split('').map(Number));
const visited = [];
const answer = [];

// 방문중인 노드의 상하좌우를 탐색하기 위한 탐색용 배열
const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

for (var i = 0; i < n; i++) {
  visited.push([]);
  for (var j = 0; j < n; j++) {
    visited[i][j] = 0;
  }
}

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (!visited[i][j] && map[i][j]) {
      bfs(i, j);
    }
  }
}

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

function bfs(x, y) {
  let count = 1; // 탐색을 시작했으므로 초기값 1로 카운트 시작
  const queue = [x, y]; // 시작 노드

  visited[x][y] = 1; // 방문 처리

  while (queue.length) {
    // queue의 길이만큼 반복
    let x = queue.shift(); // queue 에서 x값을 꺼냄
    let y = queue.shift(); // queue에서 y값을 꺼냄

    for (let i = 0; i < 4; i++) {
      // 상하좌우 총 4번의 탐색을 위해 반복
      let nx = x + dx[i]; // 현재 탐색중인 노드를 기준으로 상하좌우 x좌표
      let ny = y + dy[i]; // 현재 탐색중인 노드를 기준으로 상하좌우 y좌표
      if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
        // 지도를 벗어나지 않는 범위
        if (!visited[nx][ny] && map[nx][ny]) {
          // 방문하지 않았으며 집이 존재한다면
          queue.push(nx, ny); // queue에서 다음 노드 대기
          visited[nx][ny] = 1; // 다음 노드 방문 처리
          count++; // 단지 내 세대 수 카운트 + 1
        }
      }
    }
  }
  answer.push(count); // answer 배열에 단지 내 세대 수를 push
}