[백준] 2667. 단지번호붙이기 (자바스크립트/node.js/javascript/BFS/DFS/너비 우선 탐색/깊이 우선 탐색)

이 문제는 DFS와 BFS 방법 모두 풀 수 있다.

상하좌우로만 이동할 수 있다고 했으므로 상하좌우로 붙어있어야 연결되었다고 볼 수 있다.

 

일단 주어진 자료를 모두 배열에 담는다. 그리고 배열을 이중for문을 통해 행과 열을 돌면서 (0행0열부터 0행 1열, 0행 2열 ...) 집이 있다면(값이 1이라면) 그리고 방문한 적이 없다면 DFS 혹은 BFS를 실행하면 된다. 이 때, 탐색이 한 번 끝나게 되면 한 단지가 만들어졌다고 볼 수 있다. 왜냐하면 기본적인 DFS와 BFS도 연결되어있는 그래프를 가지고 순서대로 탐색하기 때문이다. 

 

기본적인 DFS와 BFS에서는 다음 탐색 대상은 현재 탐색 대상인 정점의 인접한 정점을 탐색했었는데 위의 경우에서는 어떻게 다음 탐색 대상을 정할 수 있을까?

 

바로 moveRow, moveCol 배열을 만들어서, 움직임을 나타내는 배열을 만들면 된다.

2차원 배열에서 (행,열) 이라고 표현한다면 현재 (2,2)에 위치했다고 했을 때 현재 좌표에서 동쪽으로 이동하는 것은 (2,3) , 서쪽으로 이동하는 것은 (2,1) , 남쪽으로 이동하는 것은 (3,2) 북쪽으로 이동하는 것은 (1,2) 를 말한다.

이것을 각각 행과 열의 움직임으로 표현하면 moveRow = [0, 0, 1, -1] , moveCol = [1, -1, 0, 0]이 된다. 

 

그렇게 해서 현재 좌표를 (row,col)이라고 하면 ((row + moveRow[n]), (col + moveCol[n])) 에 대해서 각각 다음 탐색 대상으로 정해주면 된다. 이 때 주의해야할 점은, 주어진 지도는 NxN 형태의 2차원 배열인데 행과 열이 각각 0보다 작거나 N을 넘어서면 주어진 지도의 범위를 넘어서기 때문에 이것도 체크해주어야 한다. 또한 범위에 맞더라도 값이 1이 아니거나 방문한 적이 있다면 탐색할 필요가 없기 때문에 이도 고려해야 한다. 이를 위해 방문여부를 체크하는 visited 배열도 만들어야 한다.

 

 

이를 그림으로 표현하면 다음과 같다.

 

이중 for문을 돌다가 값이 1이면 탐색을 시작하는데, 위의 지도에서는 처음 탐색 대상은 (0,1)이 될 것이다.

(0,1)의 경우 동서남북 중에서 서쪽은 값이 1이 아니므로 탐색 대상이 아니며 북쪽은 범위를 벗어나므로 탐색 대상이 아니다. 그러므로 동쪽과 남쪽이 탐색 대상이 된다.

 

여기서 DFS라면 재귀 형태로 계속해서 아래 레벨로 (깊이 우선) 탐색을 진행하므로

첫번째 단지의 경우 DFS 탐색 순서는 (0, 1) => (0, 2) => (1, 2) => (1, 1) =>(2, 1) => (2, 2) => (2, 0)가 된다.

 

BFS라면 같은 레벨부터 우선으로 (너비 우선) 탐색을 진행하니까

첫번째 단지의 경우 BFS 탐색 순서는 (0, 1) => (0, 2) => (1, 1) => (1, 2) => (2, 1) => (2, 2) => (2, 0)가 된다.

 

 

---

 

내가 작성한 코드 (자바스크립트)

1. DFS

let fs = require("fs");
let input = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(input[0]);
input.shift();
input = input.map((element) => {
  return element
    .trim()
    .split("")
    .map((element) => Number(element));
});
const visited = [];
for (let i = 0; i < N; i++) {
  visited.push(new Array(N).fill(0));
}

// x : 행 / y: 열
const moveRow = [0, 0, 1, -1]; // 동, 서, 남, 북
const moveCol = [1, -1, 0, 0]; // 동, 서, 남, 북

// 범위 체크
const rangeCheck = (row, col) => {
  if (row >= 0 && row < N && col >= 0 && col < N) {
    return true;
  }
  return false;
};

// DFS
const DFS = (row, col) => {
  if (
    rangeCheck(row, col) === true &&
    input[row][col] === 1 &&
    visited[row][col] === 0
  ) {
    // 범위안에 들어가고 && 방문한적이 없으면 DFS 탐색
    visited[row][col] = 1; // 방문 처리
    number++;
    for (let n = 0; n < moveRow.length; n++) {
      DFS(row + moveRow[n], col + moveCol[n]);
    }
  }
};

const complex = [];
let number = 0;

for (let row = 0; row < N; row++) {
  for (let col = 0; col < N; col++) {
    if (Number(input[row][col]) === 1 && visited[row][col] === 0) {
      DFS(row, col);
      complex.push(number);
      number = 0;
    }
  }
}
complex.sort((a, b) => a - b); // 오름차순으로 정렬!
const answer = [complex.length, ...complex];

console.log(answer.join("\n"));

2. BFS

let fs = require("fs");
let input = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(input[0]);
input.shift();
input = input.map((element) => {
  return element
    .trim()
    .split("")
    .map((element) => Number(element));
});
const visited = [];
for (let i = 0; i < N; i++) {
  visited.push(new Array(N).fill(0));
}

// x : 행 / y: 열
const moveRow = [0, 0, 1, -1]; // 동, 서, 남, 북
const moveCol = [1, -1, 0, 0]; // 동, 서, 남, 북

// 범위 체크
const rangeCheck = (row, col) => {
  if (row >= 0 && row < N && col >= 0 && col < N) {
    return true;
  }
  return false;
};

// BFS
const BFS = (row, col) => {
  const queue = [];
  queue.push([row, col]);
  while (queue.length) {
    const target = queue.shift();
    row = target[0];
    col = target[1];
    if (visited[row][col] === 0) {
      // 방문처리
      visited[row][col] = 1;
      number++;
      for (let n = 0; n < moveRow.length; n++) {
        if (
          rangeCheck(row + moveRow[n], col + moveCol[n]) &&
          input[row + moveRow[n]][col + moveCol[n]] === 1
        ) {
          queue.push([row + moveRow[n], col + moveCol[n]]);
        }
      }
    }
  }
};

const complex = [];
let number = 0;

for (let row = 0; row < N; row++) {
  for (let col = 0; col < N; col++) {
    if (Number(input[row][col]) === 1 && visited[row][col] === 0) {
      BFS(row, col);
      complex.push(number);
      number = 0;
    }
  }
}
complex.sort((a, b) => a - b); // 오름차순으로 정렬!
const answer = [complex.length, ...complex];

console.log(answer.join("\n"));