💡문제 분석 요약

• 문제 설명
  • 주어진 지도는 N x N 크기의 2차원 배열로 이루어져 있으며, 각 칸은 0 또는 1로 표시된다.
  • 1은 집이 있는 곳을 의미하고, 0은 집이 없는 곳을 의미한다.
  • 상하좌우로 연결된 1은 하나의 단지를 이룬다.
  • 각 단지에 속하는 집의 수를 오름차순으로 출력해야 한다.
• 입력
  • 첫째 줄에는 지도의 크기 N이 주어진다. (5 <= N <= 25)
  • 그다음 N줄에 걸쳐 각 줄에 N개의 숫자로 이루어진 지도가 주어진다.
• 출력
  • 총 단지 수와 각 단지에 속하는 집의 수를 오름차순으로 출력한다.

💡알고리즘 설계

• 그래프 탐색
  • 각 위치에서 상하좌우로 연결된 집(=1)을 찾아서 하나의 단지로 그룹화해야 한다.
  • 이를 위해 DFS 또는 BFS 탐색을 이용하여, 이미 방문한 집은 다시 탐색하지 않도록 해야 한다.
• 단지 찾기
  • 2차원 배열을 순회하면서 1을 발견하면 새로운 단지를 시작한다.
  • 해당 위치에서 DFS 또는 BFS 탐색을 시작하여 연결된 모든 집을 방문하고 단지의 크기를 계산한다.
  • 단지 크기 계산이 끝나면 그 크기를 저장하고, 다음 탐색을 진행한다.
• 알고리즘 세부 단계
  • 각 단지의 크기를 저장할 배열을 만든다.
  • 2차원 배열에서 집이 있는 칸(1)을 발견할 때마다 DFS 또는 BFS로 해당 단지에 속하는 집들을 모두 방문한다.
  • 각 단지의 크기를 계산한 후 오름차순으로 출력한다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\\n')

const N = parseInt(input[0], 10); // 첫 번째 줄은 지도의 크기 N
const map = input.slice(1).map((line) => line.split('').map(Number)); // 2차원 배열로 변환

function solution(N, map) {
  const dx = [-1, 1, 0, 0]; // 상, 하, 좌, 우
  const dy = [0, 0, -1, 1];

  const visited = Array.from({ length: N }, () => Array(N).fill(false)); // 방문 배열
  const complexes = []; // 단지별 집의 수를 저장할 배열

  // DFS 함수
  const dfs = (x, y) => {
    let count = 1; // 집 하나를 발견했으므로 초기 값 1
    visited[x][y] = true;

    // 상하좌우로 탐색
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      // 지도의 범위를 벗어나지 않도록
      if (nx >= 0 && ny >= 0 && nx < N && ny < N) {

        // 방문하지 않았고, 집이 있을 경우
        if (!visited[nx][ny] && map[nx][ny] === 1) {

          // 재귀적으로 탐색하면서 집의 수를 더해줌
          count += dfs(nx, ny);
        }
      }
    }

    return count; // 해당 단지의 총 집 수 반환
  };

  // 전체 맵 탐색
  for (let i = 0; i < N; i++) {

    for (let j = 0; j < N; j++) {

      // 집이 있는 위치에서 DFS 시작
      if (map[i][j] === 1 && !visited[i][j]) {
        const complexSize = dfs(i, j);

        complexes.push(complexSize); // 단지 크기를 저장
      }
    }
  }

  complexes.sort((a, b) => a - b); // 오름차순 정렬

  console.log(complexes.length); // 총 단지 수 출력
  complexes.forEach((size) => console.log(size)); // 각 단지의 집 수 출력
}

solution(N, map);

💡시간복잡도

• 모든 노드를 한 번씩 방문하므로 O(N^2)이다.
  • N은 지도의 크기, 최대 값은 25