[Algorithm] 백준 10026번-적록색약

백준 10026번-적록색약

문제 파악

• 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 문제 !
• 핵심은 적록색약인 사람은 R과 G가 동일하게 보인다 !

문제만 보았을 때 떠오르는 풀이방법은,,,

1. 처음부터 적록색약이 보는 구역과 아닌 사람이 보는 구역을 따로 구현해서 풀기
2. 구역은 그대로 들어가되, while문 안에서 나눠서 구현하기
3. 일단 적록색약이 아닌 사람이 봤을 때 구역구하고 생각하기

📌 백준 10026번 문제 링크

풀이 과정

• 처음에는 방법 3 → 방법 2 순으로 접근해서 풀었다 (1차 풀이)
• 풀어보니깐 방법 1이 코드가 더 간결하겠다는 생각에 다시 풀어보았다 (2차 풀이)

1차 풀이 (조건문으로 처리)

처음에는 하나의 bfs 함수에서 isRG 플래그를 통해 적록색약 여부를 구분해서 처리

isRG가 true인 경우, “G”(초록)을 모두 “R”로 바꿔서 본다는 코드를 추가

// 기준점의 color(board[x][y])가 "R"인 경우 "G"로 변경
if (isRG && color == "R") color = "G";

// newX, newY의 color인 boardColor가 "R"인 경우 "G"로 변경
if (isRG && board[nx][ny] == "R") boardColor = "G";

1차풀이 - 전체 코드

let [N, ...board] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

board = board.map((color) => color.split(""));
const visited = Array.from({ length: +N }, () => Array(+N).fill(0)); // 적록색약 X
const rgVisited = Array.from({ length: +N }, () => Array(+N).fill(0)); // 적록색약 O

const answer = [];
let count = 0;

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

const bfs = (startX, startY, vis, isRG) => {
  const queue = [[startX, startY]];
  vis[startX][startY] = 1;
  count++;

  while (queue.length > 0) {
    const [x, y] = queue.shift();
    let color = board[x][y];
    if (isRG && color == "R") color = "G";

    for (let dir = 0; dir < 4; dir++) {
      const [nx, ny] = [x + dx[dir], y + dy[dir]];
      if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
      if (!isRG && (vis[nx][ny] == 1 || board[nx][ny] !== color)) continue;

      let boardColor = board[nx][ny];
      if (isRG && board[nx][ny] == "R") boardColor = "G";
      if (isRG && (vis[nx][ny] == 1 || boardColor !== color)) continue;

      vis[nx][ny] = 1;
      queue.push([nx, ny]);
    }
  }
};

// 적록 색약 아닌 경우
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (visited[i][j] === 0) bfs(i, j, visited, false);
  }
}

answer.push(count);
count = 0;

// 적록 색약인 경우
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (rgVisited[i][j] === 0) bfs(i, j, rgVisited, true);
  }
}

answer.push(count);
console.log(answer.join(" "));

---

2차 풀이 (적록색약용 구역을 따로 처리)

내 1차 풀이를 보니, 처음부터 적록색약 시야에 맞게 구역을 변형해서 처리하는게 로직이 훨씬 깔끔해진다는 걸 느꼈다.

rgBoard = board.map((row) =>
  row.map((color) => color === "R" ? "G" : color)
);

2차 풀이 - 전체 코드

let [N, ...board] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

board = board.map((color) => color.split(""));
const visited = Array.from({ length: +N }, () => Array(+N).fill(0)); // 적록색약 X

const rgBoard = board.map((row) =>
  row.map((color) => (color === "R" ? "G" : color)),
);
const rgVisited = Array.from({ length: +N }, () => Array(+N).fill(0)); // 적록색약 O

const answer = [];
let count = 0;

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

const bfs = (startX, startY, vis, board) => {
  const queue = [[startX, startY]];
  vis[startX][startY] = 1;
  count++;

  while (queue.length > 0) {
    const [x, y] = queue.shift();
    let color = board[x][y];

    for (let dir = 0; dir < 4; dir++) {
      const [nx, ny] = [x + dx[dir], y + dy[dir]];
      if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
      if (vis[nx][ny] == 1 || board[nx][ny] !== color) continue;

      vis[nx][ny] = 1;
      queue.push([nx, ny]);
    }
  }
};

// 적록 색약 아닌 경우
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (visited[i][j] === 0) bfs(i, j, visited, board);
  }
}

answer.push(count);
count = 0;

// 적록 색약인 경우
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (rgVisited[i][j] === 0) bfs(i, j, rgVisited, rgBoard);
  }
}

answer.push(count);
console.log(answer.join(" "));

---

마무리

결론적으로 두 가지 방식 ‘정답’이 떴다ㅎㅎㅎ!!
어떤 방식이 더 직관적일지는 문제의 복잡도나 개인 스타일에 따라 달라질 수 있다. (내가 푼 두가지 방법보다 더 쉬운 방법이 있을지도 모른다) 하지만 개인적으로는 2차 풀이가 훨씬 깔끔하고 유지보수에 유리하다고 느꼈다

---

END