문제

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

크기가 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

나의 코드

const input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\n");
const N = Number(input[0]);
input.shift();
// 기존의 board
let board = input.map((r) => r.split(""));
// 적록색맹의 board : R을 G로 바꿈
let boardWeakRG = board.map((row) =>
  row.map((color) => (color === "G" ? "R" : color))
);
// 2가지 케이스의 결과를 출력
console.log(solution(board), solution(boardWeakRG));

function solution(board) {
  const dfs = (x, y, color) => {
  // out of range 처리
    if (x < 0 || y < 0 || x >= N || y >= N) return false;
    // 이미 방문한 곳은 다시 방문하지 않음
    if (board[x][y] === "X") return false;
    // 신규가 아닌 (신규 호출일 때는 color를 의도적으로 undefined로 둠), 재귀 호출했을 때만 해당(아래 코드에서 color를 할당받은 상태).
    // 이 때 다른 색의 칸을 밟을 경우 return false한다.
    if (color && board[x][y] !== color) return false;
    // 신규 호출되어 아직 color가 없을 경우 현재 밟은 땅에 써있는 색깔 (R,G,B 중 하나)이 color가 된다.
    if (!color) {
      color = board[x][y];
    }
    board[x][y] = "X";
    // 깊이 우선 탐색을 위한 재귀 호출
    dfs(x - 1, y, color);
    dfs(x + 1, y, color);
    dfs(x, y - 1, color);
    dfs(x, y + 1, color);
    // 한 영역의 탐색을 마치면 return true
    return true;
  };

  let ans = "";
  // 2중 for문으로 2차원 배열 탐색
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
    // return true일 경우에는 하나의 영역 탐색을 마친 상태이므로 ans++
      if (!dfs(i, j)) continue;
      ans++;
    }
  }
  // 답 return 후 종료
  return ans;
}

지난 시간에 풀어봤던 장미 전쟁 문제와 논리가 같지만 좀 더 현명하게 처리한 부분이 있어서 기록하려고 가져온 문제이다.

장미전쟁 문제에서 이런 부분이 있었다. (다시 보니까 가독성도 별로고, myTeam/yourTeam 따위는 불필요한 비효율적인 코드이다.)

// 신규 호출한 부분이어서 아직 team 배정이 안된 경우 team을 딱 정함. 우리팀/너네팀
  if (!team) {
    team = board[x][y] === "W" ? "myTeam" : "yourTeam";
  }

// 남의 땅을 밟으면 count할 수 없으므로 return false
  if (
    (team === "myTeam" && board[x][y] === "B") ||
    (team === "yourTeam" && board[x][y] === "W")
  ) {
    return false;
  }

아직 team이 배정되지 않았다면(재귀 호출이 아니라 신규 호출이라면) 현재 밟은 땅이 W라면 "myTeam"이라고 팀 네임을 정하고, "B"일 경우 "yourTeam"이라고 팀 네임을 정했었다.

그런데 이번에도 현재 밟은 땅이 무엇인지에 따라 재귀 호출 후 똑같은 땅을 밟아야 하는 경우이다. 즉, 논리가 동일하다. 이번에는 이 부분을 이렇게 처리했다.

// 재귀 호출한 경우 중 지금 밟은 땅이 원래 밟은 땅과 다를 경우 return false
    if (color && board[x][y] !== color) return false;
// 신규 호출한 경우 현재 밟은 땅을 color로 배정
    if (!color) {
      color = board[x][y];
    }

color는 위의 장미게임 예시에서 team에 해당한다. 현재 color와 다른 땅인 경우 return false하는 작업을 color 배정하는 것보다 먼저 하는 것이다. 다만 이렇게 하면 신규 호출 시에 color가 undefined여서 board[x][y] !== color이게 되고 return false되는 문제가 생긴다. 이를 해결하기 위해 조건문 앞부분에 color && 를 덧붙였고, 신규가 아닌 재귀 호출한 경우에 한해서만 (즉 color을 부여받은 상태에서만) 조건문을 확인하도록 설계했다.

'우리 땅만 밟자'라는 같은 논리인데 코드가 훨씬 간단해지고 가독성도 개선되었다. 앞으로 이런 논리를 또 사용할 때 참고하자!!

DFS/BFS가 중독성이 있어서 계속 풀게 된다. ㅎㅎㅎ 요즘 DFS/BFS에 집중한 것 같으니 이제 완전탐색도 많이많이 풀자 ~!~! 화이팅!!