[백준] 10026 적록색약 - javascript

📌 문제

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

📌 풀이

let input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
let n = Number(input[0]);
let arr = new Array(n);
let cnt_able = (cnt_disable = 0);
for (let i = 0; i < arr.length; i++) {
  arr[i] = input[i + 1].split("");
}
let check = new Array(n);
for (let i = 0; i < check.length; i++) {
  check[i] = new Array(n).fill(0);
}
function bfs(x, y) {
  let queue = [];
  queue.push([x, y]);
  check[x][y] = 1;
  let dx = [0, 0, 1, -1];
  let dy = [1, -1, 0, 0];
  while (queue.length) {
    let len = queue.length;
    for (let i = 0; i < len; i++) {
      let x = queue.shift();
      for (let i = 0; i < 4; i++) {
        let nx = x[0] + dx[i];
        let ny = x[1] + dy[i];
        if (
          nx >= 0 &&
          nx < n &&
          ny >= 0 &&
          ny < n &&
          !check[nx][ny] &&
          arr[x[0]][x[1]] === arr[nx][ny]
        ) {
          check[nx][ny] = 1;
          queue.push([nx, ny]);
        }
      }
    }
  }
}
// 적록색약 아닌 경우 bfs
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (!check[i][j]) {
      bfs(i, j);
      cnt_able++;
    }
  }
}
// 적록색약인 경우 빨강,초록 색깔통합시켜주기
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (arr[i][j] === "R") arr[i][j] = "G";
  }
}
// check 배열 초기화
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    check[i][j] = 0;
  }
}
// 적록색약인 경우 bfs
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (!check[i][j]) {
      bfs(i, j);
      cnt_disable++;
    }
  }
}
console.log(cnt_able, cnt_disable);

✔ 알고리즘 : BFS

✔ bfs함수를 작성하여 x,y에서 출발해서 주변의 모든 arr[x][y]색깔을 방문하고 방문했던 좌표는 check를 1로 바꾼다

✔ arr의 모든 좌표가 check가 1이 되야 모든 구역이 나누어진다. 따라서 bfs함수를 한번 호출할때마다 cnt_able++을 통해 적록색약이 아닌 경우의 구역을 증가시킨다.

✔ 적록색약은 RG를 구별못하므로 R을G로 바꾸어준다.

✔ bfs를 돌기전에 check배열을 모두 0으로 초기화시켜준다.

✔ 다시 0,0부터 bfs를 돌아서 적록색약인 경우 구역의 수를 구한다

✔ 난이도 : 백준 기준 골드5