백준 10026번 적록색약

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

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

입력 예시 1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

출력 예시 1

4 3

---

풀이/접근 방법(JavaScript)

적록색약 아닌 사람은 dfs에서 현재 컬러와 확인한 컬러가 같은지만 확인하면서 상하좌우 탐색.

적록색약의 경우 R과 G의 차이를 구분하지 못하므로, R과 G일때를 image[i][j]를 "#"으로 바꿔주어 동일하게 인식할 수 있도록 한다.

이렇게 원본 배열을 바꿔주면 위에서 사용했던 dfs 함수를 재활용 가능함.

코드(JavaScript)

// 적록색약은 인접한 R과 G를 하나로 본다.
// 출력 적록색약 X, 적록색약 O 구역의 수

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const N = Number(input.shift());
const image = input.map((item) => item.split(""));
let visited = Array.from(Array(N), () => Array(N).fill(false));
const dir = [
  [-1, 0],
  [0, 1],
  [1, 0],
  [0, -1],
];

let notCnt = 0;
let RGWeaknessCnt = 0;

// 색약아닐때
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (!visited[i][j]) {
      dfs(i, j, image[i][j]);
      notCnt++;
    }
  }
}

// 색약일때
visited = Array.from(Array(N), () => Array(N).fill(false));
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    // R, G를 #로 바꿔줌
    if (image[i][j] === "R" || image[i][j] === "G") image[i][j] = "#";
  }
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (!visited[i][j]) {
      dfs(i, j, image[i][j]);
      RGWeaknessCnt++;
    }
  }
}

function dfs(i, j, color) {
  if (isValidRange(i, j) && !visited[i][j] && image[i][j] === color) {
    visited[i][j] = true;
    for (let d of dir) {
      const [dx, dy] = [i + d[0], j + d[1]];
      dfs(dx, dy, color);
    }
  }
}

function isValidRange(i, j) {
  if (i < 0 || i >= N || j < 0 || j >= N) return false;
  else return true;
}

console.log(notCnt);
console.log(RGWeaknessCnt);

---