백준 3184 JS 풀이

구하는 값

남아있는 양, 늑대 수

핵심 아이디어

순차적으로 DFS돌면서 연결요소안에서 양과 늑대 수 세고 누가 더 많은지 비교 후 많은 수만 출력할 값에 더해줌

구현방법

1. 인접리스트 만들고, 같은크기로 visited배열만들기
2. 현재 연결요소의 양, 늑대 수를 담을 변수 생성
3. dfs 돌면서 양, 늑대 수 카운팅
4. 이중for문으로 각 위치 돌면서 dfs탐색, 양이 더 많으면 양 수 추가, 아니면 늑대 수 추가 후 양, 늑대 수 초기화

코드

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

const [r, c] = input[0].split(" ").map(Number);

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

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

// let sheep = [],wolf = [],
let sheep = 0,
    wolf = 0;

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

    if (graph[y][x] === "o") sheep++;
    if (graph[y][x] === "v") wolf++;

    for (let i = 0; i < 4; i++) {
        const ny = y + dy[i],
            nx = x + dx[i];

        if (ny < 0 || ny >= r || nx < 0 || nx >= c || graph[ny][nx] === "#") continue;

        if (!visited[ny][nx]) dfs(ny, nx);
    }
}

let ans1 = 0,
    ans2 = 0;

for (let i = 0; i < r; i++) {
    for (let j = 0; j < c; j++) {
        if (!visited[i][j] && graph[i][j] !== "#") {
            dfs(i, j);
            
            sheep > wolf ? (ans1 += sheep) : (ans2 += wolf);

            sheep = 0;
            wolf = 0;
        }
    }
}

console.log(ans1, ans2);