[백준] 1388 바닥장식

gonn-i·2024년 5월 18일

알고리즘 문풀 ✏️

목록 보기

13/35

접근 방향

같은 행에 인접한 - 나무 판자는, 하나로 인지하자.
같은 열에 인접한 | 나무 판자는, 하나로 인지하자.

이게 문제의 핵심인 것 같다. (사실 그냥 문제를 읽기만 해도 저걸 염두에 두어야 하는 것은 당연하지만)
그래서 이중 for문을 돌려서 - 판자 뒤에 뭐가 오는지, 그리고 그 다음 이중 for문에는 | 판자 뒤에는 뭐가 오는지를 판별해서 갯수를 카운트해주었다.

풀이 코드 해석

let fs = require('fs');
let filePath = process.platform === 'linux' ? '/dev/stdin' : '/input.txt';
let input = fs
  .readFileSync(__dirname + filePath)
  .toString()
  .split('\n');

let [N, M] = input.shift().split(' ');
let count = 0;
let floor = [];
let flag = false; // 같은지 여부 (쓰루 or Not)

// 나무판자 이중배열로 재구성
for (let i = 0; i < N; i++) {
  floor[i] = input[i].split('');
  for (let j = 0; j < M; j++) {}
}
// let n = 1;
// console.log(floor);

// '-' 먼저 탐색
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (floor[i][j] == '-') {
      flag = true; // '-' 뒤에 또 나오면 쓰루
    }
    if (floor[i][j] == '|' && flag) {
      // '-'가 전에 나왔으나 뒤에는 다를 경우
      flag = false;
      count++;
    }
    // console.log(n, count);
    // n++;
  }
  if (flag) {
    // 만약 특정행의 마지막이 - 인 경우 뒤에 뭐가 오든 +1
    count++;
    flag = false;
  }
}

// console.log(count); // '-' 판자 수 체크
flag = false;

// '|' 탐색 이번엔 열 단위로 탐색
for (let i = 0; i < M; i++) {
  for (let j = 0; j < N; j++) {
    if (floor[j][i] == '|') {
      flag = true;
    } else if (floor[j][i] == '-' && flag) {
      count++;
      flag = false;
    }
  }
  if (flag) {
    count++;
    flag = false;
  }
}

console.log(count); // 전체 판자 수 체크

풀이 과정에서 새롭게 느낀점(배운점)

생각보다 간단한 문제였으나, DFS로 풀어야한다..!! 라는 묘한 압박감이 있었던가?
풀고 나니 괜히 겁을 먹어 어렵게 생각하려다보니 오래걸려버렸다.
DFS/ BFS 쪽 문제를 많이 접해보지 않아 더 그랬던 것 같다.
이번주는 한 우물 정신으로 더더 많이 문제를 접해봐야겠다! 🥸

문제

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.

이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.

기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.