[백준] 10026. 적록색약 풀이 (Python, JavaScript)

10026번: 적록색약

접근한 방법

적록색약인 배열의 R값을 모두 G, 혹은 G값을 모두 R로 바꿔준 후 적록색약이 아닌 배열과 동일하게 탐색을 넣어줍니다. 모든 값에 대하여 방문이 가능한 경우에만 결괏값을 +1카운트한 후 DFS로 상하좌우를 확인해 진입 시작값과 같은 값들을 모두 방문처리 해줍니다. 2번 탐색을 하고나면 적록색약이 아닌 경우와 적록색약인 경우의 결괏값을 얻을 수 있습니다.

 

Python

import sys
sys.setrecursionlimit(4000)
input = sys.stdin.readline

n = int(input())
strings = [input().rstrip() for _ in range(n)]
arr1, arr2 = [], []
for s in strings:
    arr1.append(list(s))
    arr2.append(list(s.replace("R", "G").replace("G", "R")))
dist = ((-1, 0), (1, 0), (0, -1), (0, 1))
visited1 = [[0] * n for _ in range(n)]
visited2 = [[0] * n for _ in range(n)]

def dfs(r, c, v, arr, visited):
    if visited[r][c]:
        return False
    if arr[r][c] == v:
        visited[r][c] = 1
        for d in dist:
            nr, nc = r + d[0], c + d[1]
            if nr < 0 or nc < 0 or nr >= n or nc >= n:
                continue
            dfs(nr, nc, v, arr, visited)
    return True

r1, r2 = 0, 0
for i in range(n):
    for j in range(n):
        r1 += dfs(i, j, arr1[i][j], arr1, visited1)
        r2 += dfs(i, j, arr2[i][j], arr2, visited2)
print(r1, r2)

JavaScript

function solution(n, strings) {
  const [arr1, arr2] = [[], []];
  for (const s of strings) {
    arr1.push(s.split(""));
    arr2.push(s.replaceAll("R", "G").replaceAll("G", "R").split(""));
  }
  const dist = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  const visited1 = Array.from({ length: n }, () => Array(n).fill(0));
  const visited2 = Array.from({ length: n }, () => Array(n).fill(0));

  const dfs = (r, c, v, arr, visited) => {
    if (visited[r][c]) return false;
    if (arr[r][c] == v) {
      visited[r][c] = 1;
      for (const d of dist) {
        const [nr, nc] = [r + d[0], c + d[1]];
        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
        dfs(nr, nc, v, arr, visited);
      }
    }
    return true;
  };
  let [r1, r2] = [0, 0];
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < n; j += 1) {
      r1 += dfs(i, j, arr1[i][j], arr1, visited1);
      r2 += dfs(i, j, arr2[i][j], arr2, visited2);
    }
  }
  return [r1, r2];
}

console.log(solution(5, ["RRRBB", "GGBBB", "BBBRR", "BBRRR", "RRRRR"]));