백준 | 적록색약 | Javascript | dfs

문제

친구와 백준 문제 풀이를 진행하면서 백준 10026 적록색약 문제를 해결했습니다

일반 dfs, bfs 문제와 유사하지만, 적록색약인 경우에 대한 정답을 추가로 구해야 하는 문제입니다

제 해설을 듣고 친구가 의견을 제시해주어 해당 내용으로도 풀어보았습니다

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";

let [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");

const answer = solution(input, Number(n));
console.log(answer);

function solution(input, n) {
  const visited = Array.from({ length: n }, () => Array(n).fill(false));
  const visited2 = Array.from({ length: n }, () => Array(n).fill(false));
  let count = 0;
  let count2 = 0;
  const redGreen = ["R", "G"];

  for (let i = 0; i < n; i++) {
    for (let i2 = 0; i2 < n; i2++) {
      if (!visited[i][i2]) {
        dfs(i, i2);
        count += 1;
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let i2 = 0; i2 < n; i2++) {
      if (!visited2[i][i2]) {
        dfs2(i, i2);
        count2 += 1;
      }
    }
  }

  function dfs(y, x) {
    visited[y][x] = true;
    const dy = [0, 1, 0, -1];
    const dx = [1, 0, -1, 0];

    for (let i = 0; i < 4; i++) {
      const nextY = dy[i] + y;
      const nextX = dx[i] + x;

      if (
        nextY >= 0 &&
        nextY < n &&
        nextX >= 0 &&
        nextX < n &&
        input[nextY][nextX] === input[y][x] &&
        !visited[nextY][nextX]
      ) {
        dfs(nextY, nextX);
      }
    }
  }

  function dfs2(y, x) {
    visited2[y][x] = true;
    const dy = [0, 1, 0, -1];
    const dx = [1, 0, -1, 0];

    for (let i = 0; i < 4; i++) {
      const nextY = dy[i] + y;
      const nextX = dx[i] + x;
      if (
        nextY < 0 ||
        nextY >= n ||
        nextX < 0 ||
        nextX >= n ||
        visited2[nextY][nextX]
      )
        continue;

      if (
        redGreen.includes(input[y][x]) &&
        redGreen.includes(input[nextY][nextX])
      )
        dfs2(nextY, nextX);
      if (
        !redGreen.includes(input[y][x]) &&
        !redGreen.includes(input[nextY][nextX])
      )
        dfs2(nextY, nextX);
    }
  }

  return `${count} ${count2}`;
}

풀이

dfs() 함수를 돌아서 비색약인의 경우 정답을 구하고,
빨간색과 초록색을 같은 색으로 판단하도록 추가한 dfs2() 함수를 돕니다

적록색약의 경우 현재위치와 다음위치가 둘다 빨녹이거나, 둘다 빨녹이 아니어야 합니다

친구의 의견

dfs를 하는건 같은데 내부 코드가 달라지고 있다
dfs 돈 다음에 R을 G로 초기화하면 어때?

아 그러네;;

이 방향이 dfs() 함수를 수정하지 않고 온전하게 재사용할 수 있을 것 같습니다

의견을 반영한 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";

let [n, ...input] = fs.readFileSync(filePath).toString().trim().split("\n");
input = input.map((line) => line.split(""));

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

const answer = solution(input, Number(n));
console.log(answer);

function solution(input, n) {
  const visited = Array.from({ length: n }, () => Array(n).fill(false));
  const visited2 = Array.from({ length: n }, () => Array(n).fill(false));
  let count = 0;
  let count2 = 0;

  for (let i = 0; i < n; i++) {
    for (let i2 = 0; i2 < n; i2++) {
      if (!visited[i][i2]) {
        dfs(input, visited, i, i2);
        count += 1;
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let i2 = 0; i2 < n; i2++) {
      if (input[i][i2] === "R") {
        input[i][i2] = "G";
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let i2 = 0; i2 < n; i2++) {
      if (!visited2[i][i2]) {
        dfs(input, visited2, i, i2);
        count2 += 1;
      }
    }
  }

  return `${count} ${count2}`;
}

function dfs(input, visited, y, x) {
  visited[y][x] = true;

  for (let i = 0; i < 4; i++) {
    const nextY = dy[i] + y;
    const nextX = dx[i] + x;

    if (
      nextY >= 0 &&
      nextY < n &&
      nextX >= 0 &&
      nextX < n &&
      input[nextY][nextX] === input[y][x] &&
      !visited[nextY][nextX]
    ) {
      dfs(input, visited, nextY, nextX);
    }
  }
}

빨간색을 초록색으로 강제로 변환해주어 적록색약도 판단할 수 있도록 수정했습니다
길던 dfs2() 함수가 사라지니 코드 양 자체가 확연히 줄었습니다