[백준] 17406번 배열 돌리기 4 - 자바스크립트

문제

17406번: 배열 돌리기 4

---

 

코드

function sol(input) {
  const [N, M, K] = input[0].split(' ').map(Number);
  let boards;
  let answer = Number.MAX_SAFE_INTEGER;
  const rotateOperations = input
    .slice(1 + N)
    .map((str) => str.split(' ').map(Number));

  dfs(0, []);

  return answer;

  function dfs(L, orders) {
    if (orders.length === K) {
      boards = input.slice(1, 1 + N).map((row) => row.split(' ').map(Number));

      orders.forEach((order) =>
        rotate2DMatrixBy1Step(...rotateOperations[order])
      );

      boards.forEach((row) => {
        const min = row.reduce((acc, val) => acc + val, 0);
        answer = Math.min(answer, min);
      });
      return;
    }

    for (let i = 0; i < K; i++) {
      if (orders.includes(i)) continue;
      dfs(L + 1, [...orders, i]);
    }
  }

  function rotate2DMatrixBy1Step(r, c, s) {
    const n = 2 * s + 1;
    const startR = r - s - 1;
    const startC = c - s - 1;

    const result = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let i = 0; i < s; i++) {
      let sr = i,
        sc = i;
      for (let j = 0; j < 4; j++) {
        while (sr === i && sc >= i && sc < n - 1 - i) {
          result[sr][sc + 1] = boards[startR + sr][startC + sc];
          sc++;
        }

        while (sr >= i && sr < n - 1 - i && sc === n - 1 - i) {
          result[sr + 1][sc] = boards[startR + sr][startC + sc];
          sr++;
        }

        while (sr === n - 1 - i && sc > i && sc <= n - 1 - i) {
          result[sr][sc - 1] = boards[startR + sr][startC + sc];
          sc--;
        }

        while (sr > i && sr <= n - 1 - i && sc === i) {
          result[sr - 1][sc] = boards[startR + sr][startC + sc];
          sr--;
        }
      }
    }
    result[s][s] = boards[startR + s][startC + s];

    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
   		 boards[startR + i][startC + j] = result[i][j];
      }
    }
  }
}

const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });

 

풀이

 

문제를 해결하기 위한 절차를 파악하고, 사용할 함수를 구현해서 모두 테스트하면 쉽게 풀리는 문제다.

 

문제를 위해서는, 2가지 함수가 필요하다.

- 회전 연산의 순서를 정하는 함수

- 회전을 수행하는 함수

 

각각 하나씩 어떻게 구현할지 생각해보자.

 

회전 연산의 순서를 정하는 함수

회전 연산 갯수 K는 1~6까지의 정수다. 연산의 "순서"를 정해야 하므로 K개의 순열을 구한다.

간단하게 dfs를 통해서 순서 배열의 경우의 수를 구하고, 순서 배열의 원소의 개수가 K개일 때마다, 회전을 순서대로 수행하고 행 합계의 최솟값을 구하면 되겠다. 우리는 모든 경우의 수에 대해서 최솟값을 구해야 하므로 dfs를 끝까지 진행하면 되겠다.

 

 

회전을 수행하는 함수

(r,c) = 회전의 기준이 될 중앙 위치, s = 회전을 수행할 한쪽 크기이다.

(r-s, c-s)가 회전할 행렬의 왼쪽위 시작점이고, (r+s, c+s)가 회전할 행렬의 오른쪽 아래 끝점이다.

 

시계방향으로 1칸씩 이동

회전을 수행할 배열을 돌릴 때, 시계방향으로 1칸씩 돌린다.

 

회전할 배열은 2*s+1의 크기를 가지며, 항상 홀수개이고 s번 회전을 수행하면 된다.

그리고 마지막 (r,c)는 배열의 중앙이므로 회전의 대상이 되지 않는다.

그림과 같이 회전을 2번(= s) 수행하면 되겠다.

2회의 for문에서 윗변, 아랫변, 좌우측면 변을 이동시키는 4개의 연산을 수행하면 될 듯 하다.

이러쿵저러쿵해서 이동시킬 행과 열 위치를 기준으로 모두 이동시켜보자.

 

풀이

그래서, 회전연산 K개에 대해서 K! 개의 경우의 수를 구하고, 각 경우의 수마다 정해진 순서대로 회전연산을 수행한 결과 배열의 행의 합 최솟값을 갱신하면 정답을 구할 수 있다.

---

 

간단한 주석 첨부

function sol(input) {
  const [N, M, K] = input[0].split(' ').map(Number);
  let boards;
  let answer = Number.MAX_SAFE_INTEGER;
  const rotateOperations = input
    .slice(1 + N)
    .map((str) => str.split(' ').map(Number)); // 회전연산을 담아둔다.

  dfs(0, []);

  return answer;
	// 코드 실행은 여기서 끝난다. 밑에부터는 구현한 함수다.
    
  function dfs(L, orders) {
    if (orders.length === K) {
      boards = input.slice(1, 1 + N).map((row) => row.split(' ').map(Number));
	  // 경우의 수의 원소 갯수가 K개면 회전 연산을 수행할 것이므로, 배열 A를 복사한다.
      
      orders.forEach((order) =>
        rotate2DMatrixBy1Step(...rotateOperations[order])
      ); // 경우의수 orders의 원소를 순회하며 회전 연산을 수행한다.

      boards.forEach((row) => {
        const min = row.reduce((acc, val) => acc + val, 0);
        answer = Math.min(answer, min);
      }); // 배열 A의 행의 합 최솟값을 갱신한다.
      return;
    }

    for (let i = 0; i < K; i++) {
      if (orders.includes(i)) continue;
      dfs(L + 1, [...orders, i]);
    }
  }

  function rotate2DMatrixBy1Step(r, c, s) {
    const n = 2 * s + 1;
    const startR = r - s - 1;
    const startC = c - s - 1;
    // startR, startC는 배열A에서 회전을 시작할 행과 열이다.
	// 순서가 헷갈려서, 새로운 배열 result를 n*n 크기로 선언했다.
    // 여기에 회전 결과를 담아두고, board로 복사할 예정이다.
    
    const result = Array.from({ length: n }, () => new Array(n).fill(0));
    for (let i = 0; i < s; i++) {
      let sr = i,
        sc = i;
      // 회전 연산 당 s회만큼 반복해야 배열 내부를 모두 회전시킬 수 있다.
      // sr,sc는 시작할 지점이며, boards에서 실행해야 하므로 startR, startC와 연계한다.
      // 또한 result는 n*n크기이므로 (sr,sc)에 회전된 모습을 저장하게 된다.
      for (let j = 0; j < 4; j++) {
        while (sr === i && sc >= i && sc < n - 1 - i) {
          result[sr][sc + 1] = boards[startR + sr][startC + sc];
          sc++;
        } // 윗쪽 변 이동

        while (sr >= i && sr < n - 1 - i && sc === n - 1 - i) {
          result[sr + 1][sc] = boards[startR + sr][startC + sc];
          sr++;
        } // 오른쪽 변 이동

        while (sr === n - 1 - i && sc > i && sc <= n - 1 - i) {
          result[sr][sc - 1] = boards[startR + sr][startC + sc];
          sc--;
        } // 아랫 변 이동

        while (sr > i && sr <= n - 1 - i && sc === i) {
          result[sr - 1][sc] = boards[startR + sr][startC + sc];
          sr--;
        } // 왼쪽 변 이동
      }
    }
    result[s][s] = boards[startR + s][startC + s];
    // (r,c) 지점은 회전을 수행하지 않으므로 그대로 복사한다.

    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        boards[startR + i][startC + j] = result[i][j];
      }
    } // 회전 결과 배열을 boards 배열로 복사해주면 된다.
  }
}

const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });