[JavaScript] 백준 코딩테스트 2667. 실버 1 : 단지번호붙이기

📌  문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

📌  입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

📌  출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

📌  예제 입출력

---

📌  풀이

구할 것

• 데이터 가공
  • 1번째 줄에 주어지는 지도의 크기를 num, 2번째 줄부터 주어지는 지도의 1과 0을 complex로 선언한다.
  • 방문 여부를 확인할 지도 map을 선언한다. 
• queue 돌리기 전
  • 가로 7(0~6), 세로 7(0~6)을 기준으로 complex의 값이 1이면서 map에 방문 처리가 되지 않았을 경우 탐색을 시작한다. (dfs, bfs 둘 다 가능하다. 먼저 bfs로 접근했다.) 이중 for문으로 접근해서 [0, 0]부터 시작하게 될 거고, 조건에 맞지 않으면 [0, 1], [0, 2]... 이런 식으로 증가해 나갈 것이다. 
• bfs로 탐색하기로 했다면
  • queue를 선언하고, 전체 단지가 몇 개 있는지 담을 빈 배열 houseCount를 선언한다. 탐색을 하면서 1이 나오면 count라는 변수에 1을 더해줄거고, 모든 탐색이 끝나면 이 count를 houseCount에 push해준다.
  • 처음 [0, 0]부터 queue에 삽입한 후 map에서 해당 좌표를 방문 처리 해준다. 현재 행과 현재 열을 shift로 뽑아내고, 현재 위치에서 상하좌우로 움직일 때 조건에 맞는지 확인한다. 현재 행과 현재 열에 상하좌우로 움직여주는 부분은 nr, nc로 표현했다.
  • 위에서 말한 조건이라 함은 저 가로 7 세로 7 기준에 부합하기 위해서는 최소 0보다 크거나 같아야 하고, 0부터 시작하니 7보다는 작아야 한다. 또한 해당 좌표가 map에서 방문 되지 않아야 하고, complex 에서는 1이어야만 카운트할 수 있다. 이렇게 조건에 맞는 경우는 queue에 넣어주고, map에서 방문 처리 해주고, count++를 해준다. 즉 조건에 부합한 경우만 1칸으로 쳐주는 것이다. 
  • 이렇게 queue를 돌렸을 때 인근의 모든 1을 다 방문해 더 이상 방문할 게 없을 경우 bfs가 종료되고, 종료될 때 houseCount에 지금까지 count한 단지 수를 넣어준다.
• 이 때 bfs를 진행하게 되는 좌표는 (0, 0), (0, 4), (4, 1)며, houseCount = [7, 8, 9]가 나온다. 
• 문제에서 답을 제출할 때 오름차순으로 하라고 한다! 예제에서는 알아서 오름차순이 되어 이 부분에서 헤맸다; sort로 정렬 해주고, 총 단지 수 === houseCount.length를, 각 단지내 집의 수(7, 8, 9)를 join("\n")으로 출력하면 된다.

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

// 단지 수
const num = Number(input.shift());

// 그림 상의 1과 0
const complex = input.map((v) => v.split("").map(Number));

// 방문 여부 확인용 지도 (num*num)
const map = Array.from(Array(num), () => Array(num).fill(false));

const queue = [];
const houseCount = [];

function bfs(row, col) {
  // queue에 삽입 후 방문 처리
  queue.push([row, col]);
  map[row][col] = true;

  // 연결된 1의 개수 카운트
  let count = 0;

  while (queue.length > 0) {
  	const [currentRow, currentCol] = queue.shift();
    const dr = [-1, 1, 0, 0]; // 상하좌우
    const dc = [0, 0, -1, 1]; // 상하좌우

    for (let i = 0; i < 4; i++) {
      const nr = currentRow + dr[i];
      const nc = currentCol + dc[i];

      if (
        nr >= 0 &&
        nr < num &&
        nc >= 0 &&
        nc < num &&
        !map[nr][nc] &&
        complex[nr][nc] === 1
      ) {
        queue.push([nr, nc]); // 방문하지 않은 집인 경우 큐에 추가
        map[nr][nc] = true; // 방문 표시
      }
    }
    count++;
  }
  houseCount.push(count);
}

for (let i = 0; i < num; i++) {
  for (let j = 0; j < num; j++) {
    if (complex[i][j] === 1 && !map[i][j]) {
      bfs(i, j);
    }
  }
}
houseCount.sort((a, b) => a - b); // 집의 수를 오름차순으로 정렬
console.log(houseCount.length);
console.log(houseCount.join("\n"));

맵을 만들어놓고 어떻게 bfs를 진행해야 하는지 감이 안 잡혀서 답답했다.

 

• dfs로 탐색하기로 했다면

bfs랑 거의 똑같다. 다른 부분은 queue가 아니라 stack인 점 + shift()가 아니라 pop()인 점 뿐... 

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

// 단지 수
const num = Number(input.shift());

// 그림 상의 1과 0
const complex = input.map((v) => v.split("").map(Number));

// 방문 여부 확인용 지도 (num*num)
const map = Array.from(Array(num), () => Array(num).fill(false));

const stack = [];
const houseCount = [];

function dfs(row, col) {
  stack.push([row, col]);
  map[row][col] = true;

  let count = 0;

  while (stack.length > 0) {
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    const [currentRow, currentCol] = stack.pop();

    for (let i = 0; i < 4; i++) {
      const nr = currentRow + dr[i];
      const nc = currentCol + dc[i];

      if (
        nr >= 0 &&
        nr < num &&
        nc >= 0 &&
        nc < num &&
        !map[nr][nc] &&
        complex[nr][nc] === 1
      ) {
        stack.push([nr, nc]);
        map[nr][nc] = true;
      }
    }
    count++;
  }
  houseCount.push(count);
}

for (let i = 0; i < num; i++) {
  for (let j = 0; j < num; j++) {
    if (complex[i][j] === 1 && !map[i][j]) {
      dfs(i, j);
    }
  }
}
houseCount.sort((a, b) => a - b); // 집의 수를 오름차순으로 정렬
console.log(houseCount.length);
console.log(houseCount.join("\n"));