백준 10026 - 적록색약

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

---

입력

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

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

---

출력

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

---

예제 입력

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력

4 3

---

이 문제는 2차원 배열을 상하좌우가 연결되있는 그래프라고 생각하고 풀어야 한다. 

2차원 배열의 모든 요소를 탐색하고, 한 요소를 탐색할 때마다 주변에 자신과 색상이 동일한 영역을 끝없이 탐색해나가는 과정을 반복적으로 수행해야 한다. 여기서 자신이 영역으로 판별난 경우는 탐색하지 않아야 하죠.

 

말로 설명하자니 너무 복잡한 것 같아서, 그림으로 설명을 해보겠습니다. 네모가 R, 동그라미가 G, 세모가 B라고 가정해봅시다.

2차원 배열이므로 0,0부터 시작할 겁니다.

우선 0,0에서 자기 자신과 색이 동일한 인접한 노드를 찾아다녀야 합니다. 이 때, 탐색 알고리즘(BFS, DFS)을 사용합니다. 이렇게 자기자신과 동일한 노드를 다 탐색을 하게 되면 탐색 알고리즘은 종료되게 됩니다. 

두번째로 0, 1을 탐색하는데 이때 이미 탐색 알고리즘에 의해 탐색된 노드이므로 종료합니다.

세번째로 0, 2를 탐색하는데 이 노드는 아직 탐색되지 않은 노드이므로 이 노드를 기준으로 다시 인접한 영역의 같은 색상 노드를 탐색합니다. 

이런식으로 한 노드에 대해 인접한 영역의 같은 색상 노드를 탐색하며 자신이 탐색한 경로에 대해서는 특정 자료구조를 통해 기록을 해두는 것이죠.

---

구현된 코드

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const N = Number(input[0]);

const matrix = input.slice(1).map((r) => r.split(""));
const rgMatrix = matrix.map((row) => row.map(s => s === "R" ? "G" : s));

const dirs = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1]
];

function isValid(row, col) {
  return !(row < 0 || row >= N || col < 0 || col >= N);
}

function findArea(matrix) {
  const visited = Array.from(new Array(N), () => Array(N).fill(false))

  const dfs = (row, col, color) => {
    if (isValid(row, col) && !visited[row][col] && matrix[row][col] === color) {
      visited[row][col] = true;
      for(const [dRow, dCol] of dirs) {
        dfs(row+dRow, col+dCol, color);
      }
    }
  };


  let cnt = 0;
  for (let row = 0; row < N; row++) {
    for (let col = 0; col < N; col++) {
      if (visited[row][col] === false) { // 방문하지 않는 경우, 탐색시작!
        dfs(row, col, matrix[row][col])
        cnt++;
      }
    }
  }
  return cnt;


}

const cnt = findArea(matrix);
const rgCnt = findArea(rgMatrix);
console.log(`${cnt} ${rgCnt}`);