https://www.acmicpc.net/problem/10026
10026번: 적록색약
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)
www.acmicpc.net
📌 `작성한 코드`
// 10026
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const N = parseInt(input.shift(), 10);
const origin = input.map((str) => str.split(""));
const blind = [...origin].map((str) =>
str.map((c) => {
if (c === "G") return "R";
return c;
})
);
const dx = [1, -1, 0, 0];
const dy = [0, 0, 1, -1];
function solution() {
const answer = [0, 0];
const originVisited = Array.from({ length: N }, () => new Array(N).fill(false));
const blindVisited = Array.from({ length: N }, () => new Array(N).fill(false));
const dfs = (a, b, color, arr, visited) => {
const stack = [];
stack.push([a, b]);
while (stack.length) {
const [x, y] = stack.pop();
visited[x][y] = true;
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (arr[nx][ny] === color && !visited[nx][ny]) {
visited[nx][ny] = true;
stack.push([nx, ny]);
}
}
}
};
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (!originVisited[i][j]) {
dfs(i, j, origin[i][j], origin, originVisited);
answer[0]++;
}
}
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (!blindVisited[i][j]) {
dfs(i, j, blind[i][j], blind, blindVisited);
answer[1]++;
}
}
}
console.log(answer.join(" "));
}
solution();
📌 풀이
dfs/bfs를 사용해서 같은 색을 가진 범위의 개수를 구해주면 되는 문제이다.
적록색약일 때와, 적록색약이 아닌 경우 보이는 범위의 개수를 구해줘야 하기 때문에 dfs를 두 번 돌려서 계산해 주면 된다.
적록 색약은 R와 G의 색을 혼동하는 것이기 때문에 적록색약의 범위를 구하기 전에 G을 R로 변경한 배열을 준비해주었다.
const origin = input.map((str) => str.split(""));
const blind = [...origin].map((str) =>
str.map((c) => {
if (c === "G") return "R";
return c;
})
);
각각의 범위는 따로 탐색해야 하므로 방문 배열을 2개 선언해서 각각 접근할 수 있게 해주었다.
const originVisited = Array.from({ length: N }, () => new Array(N).fill(false));
const blindVisited = Array.from({ length: N }, () => new Array(N).fill(false));
적록 색약일 때와 아닐 때 모두 사용하고 싶어서 방문 배열, 원본 배열, 색들을 인자로 받아와서 사용할 수 있게 해주었다.
const dfs = (a, b, color, arr, visited) => {
const stack = [];
stack.push([a, b]);
while (stack.length) {
const [x, y] = stack.pop();
visited[x][y] = true;
for (let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
if (arr[nx][ny] === color && !visited[nx][ny]) {
visited[nx][ny] = true;
stack.push([nx, ny]);
}
}
}
};
우리는 범위의 개수를 구하고 싶은 것이기 때문에 dfs가 한번 끝나면 숫자를 증가시켜 범위의 개수를 세어준다.
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (!originVisited[i][j]) {
dfs(i, j, origin[i][j], origin, originVisited);
answer[0]++;
}
}
}
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (!blindVisited[i][j]) {
dfs(i, j, blind[i][j], blind, blindVisited);
answer[1]++;
}
}
}
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/DFS] 백준 실버 1 : 2583 - 영역 구하기 (0) | 2024.01.15 |
|---|---|
| [JavaScript/BFS] 백준 실버 1 : 7562 - 나이트의 이동 (0) | 2024.01.12 |
| [JavaScript/BFS] 백준 골드 5 : 7576 - 토마토 (0) | 2024.01.10 |
| [JavaScript/DFS] 백준 실버 2 : 1012 - 유기농 배추 (0) | 2024.01.08 |
| [JavaScript/BFS] 백준 실버 1 : 1926번 - 그림 (0) | 2023.10.10 |