[백준] 10026

적록색약

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

입력

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

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

출력

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

풀이

class Node {
  constructor(data, prev = null, next = null) {
    this.data = data;
    this.prev = prev;
    this.next = next;
  }
}

class Queue {
  constructor() {
    this.head = new Node(-1);
    this.tail = new Node(-1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }
  enQueue(data) {
    let node = new Node(data);
    node.next = this.tail;
    node.prev = this.tail.prev;
    this.tail.prev.next = node;
    this.tail.prev = node;
    this.size++;
  }
  deQueue() {
    if (this.ifEmpty()) return -1;
    let tmp = this.head.next;
    this.head.next = tmp.next;
    tmp.next.prev = this.head;
    this.size--;
    return tmp.data;
  }
  ifEmpty() {
    return this.size ? false : true;
  }
}

const rgb = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n");
  const size = parseInt(input[0]);
  const dir = [
    [1, 0, -1, 0],
    [0, 1, 0, -1],
  ];
  input.shift();
  input = input.map((n) => n.split(""));
  let colorBlind = 0;
  let notColorBlind = 0;
  let queue = new Queue();
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      if (input[i][j] === "B") {
        queue.enQueue([i, j]);
        input[i][j] = " ";
        colorBlind++;
        notColorBlind++;
        while (!queue.ifEmpty()) {
          let cur = queue.deQueue();
          for (let k = 0; k < 4; k++) {
            let coord = [cur[0] + dir[0][k], cur[1] + dir[1][k]];
            if (
              coord[0] < 0 ||
              coord[0] >= size ||
              coord[1] < 0 ||
              coord[1] >= size
            )
              continue;
            if (input[coord[0]][coord[1]] !== "B") continue;
            input[coord[0]][coord[1]] = " ";
            queue.enQueue([coord[0], coord[1]]);
          }
        }
      }
    }
  }
  //for not color bilnded
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      if (input[i][j] === "R" || input[i][j] === "G") {
        let color = input[i][j];
        queue.enQueue([i, j]);
        input[i][j] = "V";
        notColorBlind++;
        while (!queue.ifEmpty()) {
          let cur = queue.deQueue();
          for (let k = 0; k < 4; k++) {
            let coord = [cur[0] + dir[0][k], cur[1] + dir[1][k]];
            if (
              coord[0] < 0 ||
              coord[0] >= size ||
              coord[1] < 0 ||
              coord[1] >= size
            )
              continue;
            if (input[coord[0]][coord[1]] !== color) continue;
            input[coord[0]][coord[1]] = "V";
            queue.enQueue([coord[0], coord[1]]);
          }
        }
      }
    }
  }
  //for color blinded
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      if (input[i][j] === "V") {
        queue.enQueue([i, j]);
        input[i][j] = " ";
        colorBlind++;
        while (!queue.ifEmpty()) {
          let cur = queue.deQueue();
          for (let k = 0; k < 4; k++) {
            let coord = [cur[0] + dir[0][k], cur[1] + dir[1][k]];
            if (
              coord[0] < 0 ||
              coord[0] >= size ||
              coord[1] < 0 ||
              coord[1] >= size
            )
              continue;
            if (input[coord[0]][coord[1]] !== "V") continue;
            input[coord[0]][coord[1]] = " ";
            queue.enQueue([coord[0], coord[1]]);
          }
        }
      }
    }
  }
  console.log(`${notColorBlind} ${colorBlind}`);
};

rgb();

반성회

왜 틀렸나 했더니 input 처음 받을 때 모든 글자에 대해 split 후 size를 받아오는 바람에

10같이 두 자리 숫자는 1, 0 으로 분해돼서 모든 배열에 대해 BFS가 돌지를 못하고 있었다