[백준]17136: 색종이 붙이기(javascript)

https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

문제

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

예제 입력 1 

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

예제 출력 1 

0

---

풀이

완탐 + 백트래킹 문제였습니다.

우리는 크기별로 5장의 색종이가 존재합니다. 

당연히 가장 큰 색종이를 먼저 붙여봐야 가장 적게 붙일 확률이 높겠죠?(물론 아닐 수도 있습니다.)

저는 편의상 1을 true 0을  false로 놓고 풀이하였습니다. 즉, 스티커를 붙일 수 있는 곳은 true 아닌 곳은 false입니다.

 

로직은 이렇습니다.

1. 스티커를 붙일 수 있는가? (1인가)

  if (map[r][c])

1-2 색종이를 붙일 수 없다면?

else {
    dfs(idx + 1, cnt);
  }

색종이 cnt를 늘리지 않고 다음 idx를 확인하면 됩니다.

2. 붙일 수 있다면 크기는 어떤 걸 붙일 수 있는가? && 그 크기의 색종이가 남아있는가? (색종이는 5장씩이므로 앞에서 모두 붙였다면 붙일 수 없습니다.)

for (let size = 5; size >= 1; size--) {
      if (paperCnt[size] === 0 || !isSetPaper(r, c, size)) continue;

크기는 큰 색종이부터 붙일 수 있는지 확인합니다.

색종이를 붙일 수 있는지 확인하는 isSetPaper 함수는 아래와 같습니다.

const isSetPaper = (r, c, size) => {
  for (let i = r; i < r + size; i++) {
    for (let j = c; j < c + size; j++) {
      if (!isIn(i, j) || !map[i][j]) return false;
    }
  }
  return true;
};

size 크기의 색종이가 범위를 벗어나거나 붙일 수 없는곳에 붙게된다면 false를 반환합니다.

범위를 확인하는 isIn 함수는 아래와 같습니다.

const isIn = (r, c) => {
  return 0 <= r && r < N && 0 <= c && c < N;
};

3. 붙인다.

4. 제거한다.(원상태로 돌려 놓는 것 입니다.)

paperCnt[size]--;
setPaper(r, c, size, false);
dfs(idx + 1, cnt + 1);
paperCnt[size]++;
setPaper(r, c, size, true);

붙인다면 색종이의 개수를 줄여주고, 제거했다면 색종이 개수를 다시 늘려줘야합니다.

setPaper 함수는 아래와 같습니다. (붙인다면 false로 뗀 다면 true로)

const setPaper = (r, c, size, isPaper) => {
  for (let i = r; i < r + size; i++) {
    for (let j = c; j < c + size; j++) {
      map[i][j] = isPaper;
    }
  }
};

5. 최종 확인

if (idx >= N * N) {
    minCnt = Math.min(cnt, minCnt);
    return;
  }

index가 100을 넘었다면 (N=10) cnt와 최소 minCnt를 비교하여 최솟값을 갱신합니다.

6. 속도 향상을 위한 로직

  if (minCnt <= cnt) return;

minCnt보다 큰 cnt로 색종이를 붙이고있다면 더 이상 확인할 필요가 없습니다.

 

전체 코드

const fs = require('fs');
const filePath =
  process.platform === 'linux' ? '/dev/stdin' : '../../input.txt';
const input = fs.readFileSync(filePath).toString().split('\n');
const N = 10;
let minCnt = Infinity;
const paperCnt = Array.from({ length: 6 }, () => 5);
let map = [];

const solution = () => {
  map = input.map(row =>
    row.split(' ').map(col => {
      if (col === '0') return false;
      else return true;
    }),
  );

  dfs(0, 0);
  console.log(minCnt === Infinity ? -1 : minCnt);
};

const dfs = (idx, cnt) => {
  if (idx >= N * N) {
    minCnt = Math.min(cnt, minCnt);
    return;
  }

  if (minCnt <= cnt) return;

  const r = parseInt(idx / N);
  const c = idx % N;
  if (map[r][c]) {
    for (let size = 5; size >= 1; size--) {
      if (paperCnt[size] === 0 || !isSetPaper(r, c, size)) continue;
      paperCnt[size]--;
      setPaper(r, c, size, false);
      dfs(idx + 1, cnt + 1);
      paperCnt[size]++;
      setPaper(r, c, size, true);
    }
  } else {
    dfs(idx + 1, cnt);
  }
};

const isSetPaper = (r, c, size) => {
  for (let i = r; i < r + size; i++) {
    for (let j = c; j < c + size; j++) {
      if (!isIn(i, j) || !map[i][j]) return false;
    }
  }
  return true;
};

const setPaper = (r, c, size, isPaper) => {
  for (let i = r; i < r + size; i++) {
    for (let j = c; j < c + size; j++) {
      map[i][j] = isPaper;
    }
  }
};

const isIn = (r, c) => {
  return 0 <= r && r < N && 0 <= c && c < N;
};

solution();