[백준][node.js] 1343. 폴리오미노

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침 없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

---

💻 구현 방법

   ◾ 분석

      보드판의 X를 먼저 AAAA로 덮고 나머지는 BB로 덮어야한다.

      그리고 덮을 수 없는 경우가 언제인지 알아야 하는데, 남은 X가 1개일 때부터 생각해 보자

X 개수	덮을 수 있는지 여부
1	X
2	BB
3	X, BB로 덮어도 1개가 남음
4	AAAA
5	X, AAAA로 덮어도 1개가 남음

 

       AAAA나 BB로 부분을 커버할 수 있지만, 꼭 1개가 남게 된다.

         ✔  그러면 먼저 AAAA와 BB로 덮은 후에 X가 하나 남아있는지 확인하면 덮을 수 없는 경우를

              구분할 수 있다.

 

 

코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const board = fs.readFileSync(filePath).toString().trim().split('.');

const result = [];
let isAllCovered = true;

function coverX(str) {
  let change = str.replaceAll('XXXX', 'AAAA');
  change = change.replaceAll('XX', 'BB');

  return change.includes('X') ? 0 : change;
}

for (const char of board) {
  if (char !== '') {
    const covered = coverX(char);

    if (covered) result.push(covered);
    else {
      isAllCovered = false;
      break;
    }
  } //
  else result.push(char);
}

console.log(isAllCovered ? result.join('.') : -1);