Algorithm
[백준] 10026번: 적록색약 - Node.js (자바스크립트)
sqsung
2023. 6. 1. 06:30
1. 문제 ㅡ 10026번: 적록색약 (난이도: Gold V)
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
2. 풀이 ㅡ Node.js (자바스크립트)
const [N, ...drawing] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
const getCounts = (colorblind = false) => {
const checked = Array.from({ length: N }).map(_ => Array.from({ length: N }, () => false));
let count = 0;
const queue = [];
for (let y = 0; y < N; y++) {
for (let x = 0; x < N; x++) {
if (checked[y][x]) continue;
checked[y][x] = true;
count += 1;
queue.push([x, y]);
while (queue.length) {
const [x, y] = queue.shift();
dirs.forEach(dir => {
const xPos = x + dir[0];
const yPos = y + dir[1];
if (xPos < 0 || yPos < 0 || xPos >= N || yPos >= N || checked[yPos][xPos]) return;
if (!colorblind) {
if (drawing[y][x] !== drawing[yPos][xPos]) return;
checked[yPos][xPos] = true;
queue.push([xPos, yPos]);
} else if (
drawing[y][x] === drawing[yPos][xPos] ||
(drawing[y][x] === 'R' && drawing[yPos][xPos] === 'G') ||
(drawing[y][x] === 'G' && drawing[yPos][xPos] === 'R')
) {
checked[yPos][xPos] = true;
queue.push([xPos, yPos]);
}
});
}
}
}
return count;
};
console.log(`${getCounts()} ${getCounts(true)}`);
2-1. 풀이 설명
입력값으로 주어진 그림을 보고, 적록색약인이 있는 사람과 없는 사람이 보는 독립 색상 구역(같은 색상이 좌우상하 중 한 칸이라도 연속적으로 이어져있는 구역)의 수를 구하면 된다. 여기서 적록색약인과 일반인의 차이는 R과 G를 같은 색으로 보냐 안보냐의 차이 밖에 없다.
getCounts 라는 함수를 만들어서 매개변수로 colorblind라는 boolean 값을 받도록 했다. 이후 BFS 탐색을 하면서 colorblind인 경우와 colorblind가 아닌 경우를 분리해 큐에 새로운 좌표를 넣을지 말지에 대한 조건을 달아줬다. 즉, 매개변수로 받은 colorblind 값이 true인 경우에는 기준 좌표가 R, 인접칸이 G, 아니면 기준 좌표가 G, 인접칸이 R인 경우에도 queue에 새 좌표 값을 추가해줬다.