백준 1388 JS 풀이

구하는 값

-, | 의 개수

핵심 아이디어

연결된 것은 1개로 본다.

구현방법

DFS풀이

DFS파리미터로 item을 받아서 동일한 값인지 검사 후 그 방향으로 DFS탐색함

이중for문

for(가로){
for(세로)
}
를 돌며 - 개수를 세고

for(세로){
for(가로)
}
를 돌며 | 개수를 셈
이때 connect변수를 이용해서 연속으로 나올때만 카운팅해줌

코드

dfs

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

const [n, m] = input[0].split(" ").map(Number);

const graph = [];
for (let i = 1; i <= n; i++) graph.push(input[i].split(""));
const visited = Array.from({ length: n }, () => new Array(m).fill(false));
const d = [-1, 1];

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

    if (item === "|") {
        for (let i = 0; i < 2; i++) {
            const ny = y + d[i];
            if (ny < 0 || ny >= n) continue;
            if (!visited[ny][x] && graph[ny][x] === "|") dfs(ny, x, item);
        }
    } else {
        for (let i = 0; i < 2; i++) {
            const nx = x + d[i];
            if (nx < 0 || nx >= m) continue;
            if (!visited[y][nx] && graph[y][nx] === "-") dfs(y, nx, item);
        }
    }
}

let cnt = 0;
// 세로
for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        if (!visited[i][j]) {
            cnt++;
            graph[i][j] === "-" ? dfs(i, j, "-") : dfs(i, j, "|");
        }
    }
}

console.log(cnt);

이중for문

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

const [n, m] = input[0].split(" ").map(Number);
const graph = [];
for (let i = 1; i <= n; i++) graph.push(input[i].split(""));

let cnt = 0;

// 가로판단 ("-")
for (let i = 0; i < n; i++) {
    // cnt시작
    let connect = true;
    for (let j = 0; j < m; j++) {
        // 연결
        if (connect && graph[i][j] === "-") {
            cnt++;
            connect = false;
        }
        // 연결끊김 -> 다시 시작
        else if (graph[i][j] === "|") connect = true;
    }
}

// 세로판당 ("|")
for (let i = 0; i < m; i++) {
    let connect = true;
    for (let j = 0; j < n; j++) {
        if (connect && graph[j][i] === "|") {
            cnt++;
            connect = false;
        } else if (graph[j][i] === "-") connect = true;
    }
}

console.log(cnt);

시간은 이중for문이 더 빠르게 나옴 근데 n,m이 커지면 시간복잡도 상으로 dfs가 더 빠를 듯함