[백준] 14719 빗물 (Javascript)

문제

BOJ14719_빗물

풀이

요구사항

빗물이 얼마나 고이는지 구하시오.

왼쪽과 오른쪽이 블럭으로 막혀있을 때 그 사이에 빈 칸이 있으면 빈 칸에 물이 고인다.

예를들어 블럭=1, 빈 칸=0 일때 [1,0,0,0,1] 이렇게 되어 있으면 양쪽이 블럭으로 막혀있고 그 사이에 빈 칸(0)이 3칸 있으니 빗물은 3만큼 고이게 된다.

만약 [1,0,0,1,0] 이렇게 되어 있다면 마지막 빈 칸은 양쪽이 블럭으로 막혀있지 않으므로 물이 고이지 않게 되고, 두 번째, 세 번째 칸은 양쪽이 블럭으로 막혀있으므로 물이 고이게 되어 빗물은 2만큼 고이게 된다.

해결방안

우선 주어진 입력값을 토대로 W*H 크기의 2차원 배열을 만들고, 블록이 있는 칸은 1로 채워주고, 빈 칸은 0으로 채워준다.

const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [H, W] = input[0].split(' ').map(Number);
const heights = input[1].split(' ').map(Number);
const map = Array.from({ length: H }, () => Array(W).fill(0));
for (let i = 0; i < W; i++) {
    for (let j = 0; j < heights[i]; j++) {
        map[j][i] = 1;
    }
}

그리고 2차원 배열을 한 칸씩 탐색하며 블록을 발견할 경우 재귀를 시작한다.

for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        // 해당 위치에 블록이 있을 경우
        if (map[i][j]) {
            dfs(i, j + 1);
            flag = false;
        }
    }
}

재귀함수는 x축을 1씩 증가시키며 블록을 발견할 때까지 반복하거나, 범위를 벗어날 때까지 반복한다.

let flag = false;
let answer = 0;

function dfs(y, x) {
    // 범위를 벗어났을 경우
    if (x >= W) return;
    // 블록을 만났을 경우
    if (map[y][x]) {
        flag = true;
        return;
    }
    dfs(y, x + 1);
    // 끝이 블록으로 막혀있을 경우
    if (flag) {
        answer++;
    }
}

만약 블록을 발견했다면 flag를 true로 만들고 재귀를 종료한다. 재귀를 탈출했을 때, flag가 true로 되어 있다면 양쪽이 블럭으로 막혀있는 것이므로 물을 채울 수 있다. 따라서 answer를 1씩 증가시킨다.

이 과정을 반복하면 정답을 구할 수 있다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [H, W] = input[0].split(' ').map(Number);
const heights = input[1].split(' ').map(Number);
const map = Array.from({ length: H }, () => Array(W).fill(0));
let flag = false;
let answer = 0;

for (let i = 0; i < W; i++) {
    for (let j = 0; j < heights[i]; j++) {
        map[j][i] = 1;
    }
}

function dfs(y, x) {
    // 범위를 벗어났을 경우
    if (x >= W) return;
    // 블록을 만났을 경우
    if (map[y][x]) {
        flag = true;
        return;
    }
    dfs(y, x + 1);
    // 끝이 블록으로 막혀있을 경우
    if (flag) {
        answer++;
    }
}

for (let i = 0; i < H; i++) {
    for (let j = 0; j < W; j++) {
        // 해당 위치에 블록이 있을 경우
        if (map[i][j]) {
            dfs(i, j + 1);
            flag = false;
        }
    }
}

console.log(answer);