[백준] 1388. 바닥 장식

https://www.acmicpc.net/problem/1388

최종 제출

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

const [width, height] = input[0].split(" ");
input.splice(0, 1);
let field = input.map(str => str.split(""));

// 방문 노드 저장
const visitArray = [...field].map(arr => [...arr].fill(false));

const dfs = (x, y, prevTile) => {
  visitArray[x][y] = true;

  // 어떤 타일이냐에 따라 증가할 방향을 정한다. 
  const [dx, dy] = prevTile === "-" ? [0, 1] : [1, 0];
  const [nx, ny] = [x + dx, y + dy];

  // 증가된 좌표가 width와 height을 넘지 않으며, 방문한 적이 없고, 같은 타일이면 방문한다.
  if (nx < width && ny < height && !visitArray[nx][ny] && field[nx][ny] === prevTile) {
    dfs(nx, ny, prevTile)
  }

};

let count = 0;
for (let i = 0; i < width; i++) {
  for (let j = 0; j < height; j++) {
    // 방문된 적이 없는 타일이면 방문한다.
    if (!visitArray[i][j]) {
      // 방문한 타일부터 인접 타일을 재검색한다.
      dfs(i, j, field[i][j]);
        
      // 재귀에서 빠져 나오면 count 증가
      count++;
    }
  }
}

console.log(count);

DFS 알고리즘을 공부 후 처음 풀어 본 알고리즘이다.
DFS 알고리즘 자체는 이해가 쉬워서 이를 활용한 문제도 쉽겠지 하고 바로 도전해 봤는데.. 다른 DFS 문제에 비해 쉬워 보이는 문제임에도 꽤나 고생했다.

노드에서 검사해야 할 방향이 오른쪽과 아래밖에 없어서 그나마 풀만했던 것 같다. 그래도 아직 나에게는 너무 어렵다 흑흑.