[JS][백준]14600_샤워실 바닥 깔기 (Small)

문제 번호

14600번: 샤워실 바닥 깔기 (Small)

 

 

 

알고리즘 분류

• 구현
• 분할 정복

 

문제 풀이

 백트래킹, 브루트포스를 사용하면 된다.

빈 공간을 발견할때마다 4가지 도형을 넣어보면서 문제에서 주어진 조건대로 모든 칸을 채울 수 있는지 백트래킹으로 확인해보면 된다.

 그래서 주어진 4가지 도형을 나타낼 배열을 사용했다. (가운데가 현재 좌표이다)

// 1,2,3,4 모양
  let dx = [[0, 0, 1], [0, 1, 1], [0, 0, -1], [0, -1, - 1]];
  let dy = [[0, -1, -1], [0, 0, 1], [0, 1, 1], [0, 0, -1]];

....;;;;

 

 문제에서 주어진 크기의 샤워실을 탐색하다가 0이 아닌 곳이 나올 때마다 1,2,3,4 순서로 도형을 넣어보고 조건에 부합하지 않을 때는 백트래킹으로 돌아오면서 답이 나올 때까지 모든 경우를 확인해본다.

 

 이후 모든 칸을 채웠을때 출력을 해야 한다.

이때 문제에서는 왼쪽 맨 아래칸이 (1,1)이고 오른쪽 가장 윗 칸이 (2^k,2^k)라고 하였으므로 좌표를 조절해서 출력해야 한다. 나는 왼쪽 위가 (1,1) 오른쪽 맨 아래가 (2^k,2^k)로 놓고 입력을 받았으므로 다음과 같이 출력하였다.

function print(map) {
  // print
  for (let i = 2 ** K - 1; i >= 0; i--) {
    let temp = '';
    temp += map[i].join(' ');
    console.log(temp)
  }
  return process.exit(0);
}

 

전체 코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');
const K = +input[0];
const [x, y] = input[1].split(' ').map(Number);

function main() {
  let map = new Array(2 ** K).fill(null).map(_ => new Array(2 ** K).fill(0));
  let cnt = (2 ** K) ** 2 - 1;
  map[y - 1][x - 1] = -1;  
  sol(map, cnt, 1);
}
function sol(map, cnt, block) {  //맵, 남은 블록 수, 현재 블록 번호.    
  if (cnt === 0)
    return print(map);

  // 1,2,3,4 모양
  let dx = [[0, 0, 1], [0, 1, 1], [0, 0, -1], [0, -1, - 1]];
  let dy = [[0, -1, -1], [0, 0, 1], [0, 1, 1], [0, 0, -1]];

  for (let i = 0; i < 2 ** K; i++) {  //빈공간 확인
    for (let j = 0; j < 2 ** K; j++) {  //빈공간 확인
      if (map[i][j] === 0) {
        for (let next = 0; next < 4; next++) {  //들어갈 수 있는 모양 확인.
          let check = true;
          for (let k = 0; k < 3; k++) {
            let nextY = i + dy[next][k];
            let nextX = j + dx[next][k];
            if (nextX < 0 || nextY < 0 || nextX >= 2 ** K || nextY >= 2 ** K || map[nextY][nextX] !== 0) {
              check = false;
              break;
            }
          }
          if (check) {  //들어갈 수 있다면 집어넣고 맵정보 갱신.
            for (let k = 0; k < 3; k++) {
              let nextY = i + dy[next][k];
              let nextX = j + dx[next][k];
              map[nextY][nextX] = block;
              cnt--;
            }
            sol(map, cnt, block + 1);
            for (let k = 0; k < 3; k++) { //맵정보 원복.
              let nextY = i + dy[next][k];
              let nextX = j + dx[next][k];
              map[nextY][nextX] = 0;
              cnt++;
            }
          }
        }
      }
    }
  }
}
function print(map) {
  // print
  for (let i = 2 ** K - 1; i >= 0; i--) {
    let temp = '';
    temp += map[i].join(' ');
    console.log(temp)
  }
  return process.exit(0);
}
main();

특이사항