[백준] 14719 빗물 - node.js

14719번: 빗물

다른 분들이 훨씬 더 간단하게 푼 것 같습니다. 양쪽 벽 중 짧은 쪽을 선택하여 세로로 빗물 양을 세는 방식이더라고요. 저는 가로로 세는 방식으로 풀었는데, 코드가 좀 복잡하지만 여기에 남깁니다.

POINT

• 블록 좌표를 따로 저장하여 왼쪽 아래 블록부터 오른쪽 위 블록 순서대로 검사한다.
• 각 블록에서 출발하여 오른쪽 방향으로 검사하며 빗물 양을 카운트한다. 

• 검사하다가 다른 블록을 만나면, 이제까지 센 빗물 양(count)을 answer 변수에 저장하고 count를 초기화한다.
• 다른 블록을 만나지 못하고 끝에 다다르면, 이제까지 센 빗물 양(count)을 저장하고 않고 초기화한다.

문제풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const [h, w] = input[0].split(" ").map(Number);
const data = input[1].split(" ").map(Number);

let graph = Array.from(Array(h), () => Array(w).fill(0)); // 빈칸은 0
let blockList = []; // 블록 좌표
// 그래프에 블록(1) 세우기
for (let y = 0; y < w; y++) {
  for (let x = h - 1; x >= h - data[y]; x--) {
    graph[x][y] = 1;
    blockList.push([x, y]); // 블록 좌표 저장
  }
}

let count = 0; // 이제까지 센 빗물 양
let answer = 0;

// 모든 블록 검사
while (blockList.length) {
  const [x, startY] = blockList.pop();

  // 블록에서 시작하여 오른쪽으로 검사
  for (let y = startY + 1; y < w; y++) {
    // 물을 만나면 카운트
    if (graph[x][y] === 0) {
      count++;
    } else {
      // 블록을 만나면
      // 이제까지 센 빗물 저장
      answer += count;
      count = 0; // 초기화
      break; // 다음 블록으로 넘어가기
    }
  }
  count = 0; // 블록을 만나지 못한 빗물 버리기
}

console.log(answer);