백준 10026 JS 문제풀이

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

구하는 값

상하좌우에 같은 값을 가지고 있는 연결요소 쌍의 개수
1. 주어진 graph,
2. R === G로 했을때 graph

핵심 아이디어

N * N 크기이고 N < 100이므로 DFS, BFS 가능

연결요소의 개수를 새는 문제
1. 방문하지 않은 노드를 만날때 cnt++를해주고 DFS를 호출
2. DFS는 해당 위치에서 연결된 모든 노드를 재귀적으로 탐색하며 방문처리

코드

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input[0]);

const graph = [],
    graph2 = [];
const visited = Array.from({ length: N }, () => new Array(N).fill(false));
const visited2 = Array.from({ length: N }, () => new Array(N).fill(false));
let cnt1 = 0;
cnt2 = 0;

for (let i = 1; i <= N; i++) {
    const arr = input[i].split("");
    graph.push(arr);

    const arr2 = arr.map((v) => {
        if (v === "R") return "G";
        else return v;
    });
    graph2.push(arr2);
}

// console.log(graph, graph2);

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

for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        if (!visited[i][j]) {
            cnt1++;
            // console.log("cnt : ", cnt);
            // console.log(visited);
            dfs(i, j, graph, visited);
        }

        if (!visited2[i][j]) {
            cnt2++;
            dfs(i, j, graph2, visited2);
        }
    }
}

function dfs(y, x, graph, visited) {
    visited[y][x] = true;

    // console.log("y, x", y, x);
    const cur = graph[y][x];
    for (let i = 0; i < 4; i++) {
        const nx = x + dx[i],
            ny = y + dy[i];

        if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;

        // console.log("ny, nx", ny, nx);
        if (!visited[ny][nx] && cur === graph[ny][nx]) dfs(ny, nx, graph, visited);
    }
}

console.log(cnt1, cnt2);