[JS][백준]17406_배열 돌리기4

문제 번호

17406번: 배열 돌리기 4

 

 

 

알고리즘 분류

구현, 브루트포스

 

문제 풀이

 브루트포스를 이용하여 문제에서 주어진 연산들을 수행할 모든 순서를 정한다. 나는 이 순서들을 operationOrder 라는 배열에 넣어주기로 하였다.

// 회전 연산의 경우의 수.
let operationOrder = [];
let end = K;
function BTS() {
  if (end === 0) {
    //console.log(operationOrder);
    return rotate();
  }

  else {
    for (let i = 0; i < operation.length; i++) {
      if (operation[i].used === false) {
        operation[i].used = true;
        operationOrder.push(operation[i]);
        end--;
        BTS();
        operation[i].used = false;
        operationOrder.pop();
        end++;
      }
    }
  }
}

 

모든 연산을 수행하였다면 문제에서 요구하는대로 배열을 돌려야한다. 나는 각모서리(오른쪽위, 오른쪽아래, 왼쪽아래)를 변수를 선언하여 미리 저장해두고 배열을 돌리기로 하였다. 각 모서리일때만 미리 저장해둔 변수를 사용하여 배열을 돌려준다면 어렵지 않게 배열을 회전시킬 수 있다.

 가장 바깥쪽 배열을 회전시켰다면 한 단계 안쪽의 배열을 회전시켜야한다. 나는 start 와 end 라는 객체를 생성해서 왼쪽위를 start 좌표로 보고 오른쪽 아래를 end 좌표로 보았다. 가장 바깥쪽 배열을 회전시키고나면 start.x++ start.y+= end.x++ end.y++ 를 통하여 한 단계 안쪽의 배열로 접근 할 수 있다.

 문제에서 정사각형 모양의 배열을 회전한다고 하였으므로 start 와 end의 좌표가 같아질때까지 계속 진행하면된다.

// 회전 연산 진행하기.
function rotate() {
  // BTS를 통해서 구한 회전연산의 순서대로 진행하기.
  for (let j = 0; j < operationOrder.length; j++) {
    let start = {
      'x': operationOrder[j].C - operationOrder[j].S,
      'y': operationOrder[j].R - operationOrder[j].S
    }
    let end = {
      'x': operationOrder[j].C + operationOrder[j].S,
      'y': operationOrder[j].R + operationOrder[j].S
    }

    while (start.x !== end.x && start.y !== end.y) {
      let
        leftTop = map[start.y][start.x],
        rightTop = map[start.y][end.x],
        rightBot = map[end.y][end.x],
        leftBot = map[end.y][start.x];


      // 가장 윗줄.
      for (let i = end.x; i > start.x; i--) {
        map[start.y][i] = map[start.y][i - 1];
      }

      // 오른쪽
      for (let i = end.y; i > start.y; i--) {
        if (i === start.y + 1)
          map[i][end.x] = rightTop;
        else
          map[i][end.x] = map[i - 1][end.x];
      }

      // 아래쪽
      for (let i = start.x; i < end.x; i++) {
        if (i === end.x - 1)
          map[end.y][i] = rightBot;
        else
          map[end.y][i] = map[end.y][i + 1];
      }

      // 왼쪽
      for (let i = start.y; i < end.y; i++) {
        if (i === end.y - 1)
          map[i][start.x] = leftBot;
        else
          map[i][start.x] = map[i + 1][start.x];
      }

      start.x++;
      start.y++;
      end.x--;
      end.y--;
    }
  }
  sumOfRow();
  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
      map[i][j] = arr[i][j];
    }
  }
}

 

이제 마지막으로 회전연산이 완료된 행렬의 값을 구해야한다.

// 행렬에서 행의 합 구하기.
function sumOfRow() {
  for (let i = 1; i <= N; i++) {
    let sum = 0;
    for (let j = 1; j <= M; j++) {
      sum += map[i][j];
    }
    if (sum < answer)
      answer = sum;
  }
}

 

전체코드

const { log } = require('console');
const { ENXIO } = require('constants');
const fs = require('fs');
const { rootCertificates } = require('tls');
const input = fs.readFileSync('배열 돌리기4/input.txt').toString().trim().split('\n');

let answer = Infinity;

const NMK = input.shift().split(' ');
const N = Number(NMK[0]);
const M = Number(NMK[1]);
const K = Number(NMK[2]);

const arr = new Array(N + 1);
let map = new Array(N + 1);
for (let i = 0; i < N + 1; i++) {
  arr[i] = new Array(M + 1);
  map[i] = new Array(M + 1);
}
for (let i = 1; i <= N; i++) {
  let temp = input.shift().trim().split(' ');
  for (let j = 1; j <= M; j++) {
    arr[i][j] = Number(temp[j - 1]);
    map[i][j] = arr[i][j];
  }
}

let operation = new Array(K);
for (let i = 0; i < K; i++) {
  const RCS = input.shift().split(' ');
  operation[i] = {
    'R': Number(RCS[0]),
    'C': Number(RCS[1]),
    'S': Number(RCS[2]),
    'used': false
  }
}

// 행렬에서 행의 합 구하기.
function sumOfRow() {
  for (let i = 1; i <= N; i++) {
    let sum = 0;
    for (let j = 1; j <= M; j++) {
      sum += map[i][j];
    }
    if (sum < answer)
      answer = sum;
  }
}

// 회전 연산 진행하기.
function rotate() {
  // BTS를 통해서 구한 회전연산의 순서대로 진행하기.
  for (let j = 0; j < operationOrder.length; j++) {
    let start = {
      'x': operationOrder[j].C - operationOrder[j].S,
      'y': operationOrder[j].R - operationOrder[j].S
    }
    let end = {
      'x': operationOrder[j].C + operationOrder[j].S,
      'y': operationOrder[j].R + operationOrder[j].S
    }

    while (start.x !== end.x && start.y !== end.y) {
      let
        leftTop = map[start.y][start.x],
        rightTop = map[start.y][end.x],
        rightBot = map[end.y][end.x],
        leftBot = map[end.y][start.x];


      // 가장 윗줄.
      for (let i = end.x; i > start.x; i--) {
        map[start.y][i] = map[start.y][i - 1];
      }

      // 오른쪽
      for (let i = end.y; i > start.y; i--) {
        if (i === start.y + 1)
          map[i][end.x] = rightTop;
        else
          map[i][end.x] = map[i - 1][end.x];
      }

      // 아래쪽
      for (let i = start.x; i < end.x; i++) {
        if (i === end.x - 1)
          map[end.y][i] = rightBot;
        else
          map[end.y][i] = map[end.y][i + 1];
      }

      // 왼쪽
      for (let i = start.y; i < end.y; i++) {
        if (i === end.y - 1)
          map[i][start.x] = leftBot;
        else
          map[i][start.x] = map[i + 1][start.x];
      }

      start.x++;
      start.y++;
      end.x--;
      end.y--;
    }
  }
  sumOfRow();
  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= M; j++) {
      map[i][j] = arr[i][j];
    }
  }
}


// 회전 연산의 경우의 수.
let operationOrder = [];
let end = K;
function BTS() {
  if (end === 0) {
    //console.log(operationOrder);
    return rotate();
  }

  else {
    for (let i = 0; i < operation.length; i++) {
      if (operation[i].used === false) {
        operation[i].used = true;
        operationOrder.push(operation[i]);
        end--;
        BTS();
        operation[i].used = false;
        operationOrder.pop();
        end++;
      }
    }
  }
}

BTS();
console.log(answer);

특이사항

 구현문제는 풀고나면 매우 간단하다고 생각되는데 막상 풀어보면 시간이 너무 오래걸린다.

더 집중해서 풀어보자.