[BOJ] 10026: 적록색약 / JS

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

 

 

 

 

const [n, ...input] = require('fs')
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split('\n');
const map = input.map((x) => x.trim().split(''));
const visit = new Array(n);
for (let i = 0; i < n; i++) visit[i] = Array.from({ length: n }, () => 0);

const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

function isRange(x, y) {
  return x >= 0 && x < n && y >= 0 && y < n;
}

function isVisit(x, y) {
  return visit[x][y];
}

function bfs(i, j) {
  const queue = [[i, j]];
  visit[i][j] = 1;
  while (queue.length) {
    const [x, y] = queue.shift();
    for (let k = 0; k < 4; k++) {
      const nx = x + dx[k];
      const ny = y + dy[k];
      if (!isRange(nx, ny) || isVisit(nx, ny) || map[x][y] !== map[nx][ny])
        continue;
      queue.push([nx, ny]);
      visit[nx][ny] = 1;
    }
  }
}

const answer = [0, 0];
function solution() {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (visit[i][j]) continue;
      bfs(i, j);
      answer[0]++;
    }
  }

  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) {
      if (map[i][j] === 'R') map[i][j] = 'G';
      visit[i][j] = 0;
    }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (visit[i][j]) continue;
      bfs(i, j);
      answer[1]++;
    }
  }
  console.log(answer.join(' '));
}
solution();

"10026: 적록색약"은  각 구역을 세는 문제이기 때문에 BFS를 사용해서 한 구역을 순회할 때마다 카운트하면 문제를 해결할 수 있다.

 

아직 방문하지 않은 셀이면 bfs 함수를 호출한다.

bfs 함수는 현재 위치에서 상하좌우에 있는 셀들에 대한 유효성 검사를 진행하고, 통과하면 큐에 담아서 그래프를 순회한다.

유효성 검사에서는 인덱스 범위와 방문 여부뿐만 아니라 map[x][y]와 map[nx][ny]를 비교해서 이웃한 셀의 색이 현재 색과 일치하는지 확인한다.

 

이렇게 첫 번째 반복문은 색약이 없는 사람이 보는 구역의 개수를 구하게 된다.

이제 색약이 있는 사람이 보는 구역의 개수를 구하기 위해 visit 배열을 0으로 초기화하고,

map에서 'R' 또는 'G'를 둘 중 하나로 대체시킨다.

색약이 있는 사람은 빨강과 초록을 구분하지 못하기 때문에 하나의 색상으로 대체할 수 있다.

 

이후 다시 첫 번째 반복문과 똑같이 bfs 함수를 호출하면 색약이 있는 사람이 보는 구역의 개수를 구할 수 있다.