[JavaScript/DFS] 백준 골드 5 : 10026 - 적록색약

https://www.acmicpc.net/problem/10026

10026번: 적록색약

---

📌 `작성한 코드`

// 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]++;
            }
        }
    }

 

---

✅ 성공