[백준] 17406 배열 돌리기 4 (Javascript)

잭슨·2024년 4월 25일

구현 백준 브루트포스 알고리즘 자바스크립트

알고리즘 문제 풀이

목록 보기

89/130

문제

BOJ17406_배열 돌리기

풀이

요구 사항

2차원 배열이 있고, k개의 연산이 주어진다.

각 연산마다 사각형의 왼쪽 위와 오른쪽 아래 지점의 좌표가 주어지고, 이 사각형을 시계 방향으로 회전시켜야 한다.

최종적으로 모든 연산을 다 수행했을 때, 사각형의 각 행의 합중 최솟값을 출력해라.

(회전)연산의 순서에 따라 최솟값이 달라질 수 있다.

접근 방식

크게 로직을 나눠보면 이렇게 나눌 수 있을 것 같다.

사각형 회전
사각형을 회전시켰을 때 각 행의 최소합 구하기
모든 연산의 순서를 구하기 위해 완전탐색(순열) 사용

연산의 개수(k)는 6보다 작거나 같기 때문에 순열을 사용했을 때 $O(6!) = 720$ 이므로 사용해도 된다.

순열 구현

for (let i = 0; i < K; i++) {
    if (!visited[i]) {
        visited[i] = true;
        permutation(i, 1, copyArr);
        visited[i] = false;
    }
}

function permutation(cur, depth, copyArr) {
    let copyArr2 = JSON.parse(JSON.stringify(copyArr));

    let [r, c, s] = operation[cur];
    let lt = [r - s - 1, c - s - 1]; // 왼쪽 위
    let rb = [r + s - 1, c + s - 1]; // 오른쪽 아래
    let rt = [lt[0], rb[1]]; // 오른쪽 위
    let lb = [rb[0], lt[1]]; // 왼쪽 아래

    // 회전 연산 수행
    while (true) {
        if (lt[0] > rb[0] || lt[1] > rb[1]) break;
        copyArr2 = rotate(lt, rb, rt, lb, copyArr2);
        lt[0]++;
        lt[1]++;
        rb[0]--;
        rb[1]--;
        rt = [lt[0], rb[1]];
        lb = [rb[0], lt[1]];
    }

    // 하나의 순열을 다 탐색했을 경우
    if (depth === K) answer = Math.min(answer, checkMin(copyArr2));

    for (let i = 0; i < K; i++) {
        if (!visited[i]) {
            visited[i] = true;
            permutation(i, depth + 1, copyArr2);
            visited[i] = false;
        }
    }
}

permutation 함수의 매개변수는 아래와 같다.
cur: 현재 인덱스
depth: 하나의 순열이 완성되었을 때, 최솟값을 확인하기 위해 깊이 정보를 갱신하기 위한 변수
copyArr: 얕은 복사된 변수

추가로 permutation 함수 내부에서 원본 배열을 변경하면 값이 달라지기 때문에 배열을 깊은 복사한다.

let copyArr2 = JSON.parse(JSON.stringify(copyArr));

좌상단,우하단,우상단,좌하단 좌표를 저장해놓는다.

let [r, c, s] = operation[cur];
let lt = [r - s - 1, c - s - 1]; // 왼쪽 위
let rb = [r + s - 1, c + s - 1]; // 오른쪽 아래
let rt = [lt[0], rb[1]]; // 오른쪽 위
let lb = [rb[0], lt[1]]; // 왼쪽 아래

하나의 순열을 다 탐색했을 경우 최솟값을 구한다.

if (depth === K) answer = Math.min(answer, checkMin(copyArr2));

아직 다 탐색하지 않았다면 마저 탐색한다.

for (let i = 0; i < K; i++) {
        if (!visited[i]) {
            visited[i] = true;
            permutation(i, depth + 1, copyArr2);
            visited[i] = false;
        }
    }

회전 구현

function rotate(lt, rb, rt, lb, copyArr) {
    const copyArr2 = JSON.parse(JSON.stringify(copyArr));
    for (let i = lt[1] + 1; i <= rt[1]; i++) {
        copyArr2[lt[0]][i] = copyArr[lt[0]][i - 1];
    }
    for (let i = rt[0] + 1; i <= rb[0]; i++) {
        copyArr2[i][rt[1]] = copyArr[i - 1][rt[1]];
    }
    for (let i = rb[1] - 1; i >= lb[1]; i--) {
        copyArr2[rb[0]][i] = copyArr[rb[0]][i + 1];
    }
    for (let i = lb[0] - 1; i >= lt[0]; i--) {
        copyArr2[i][lb[1]] = copyArr[i + 1][lb[1]];
    }
    return copyArr2;
}

최솟값 구하는 함수 구현

function checkMin(arr) {
    let min = Infinity;
    for (let row of arr) {
        min = Math.min(
            min,
            row.reduce((acc, cur) => (acc += cur))
        );
    }
    return min;
}

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs')
    .readFileSync(filePath)
    .toString()
    .trim()
    .split('\n')
    .map((e) => e.split(' ').map(Number));
const [N, M, K] = input[0];
const arr = input.slice(1, N + 1);
const copyArr = JSON.parse(JSON.stringify(arr));
const operation = input.slice(N + 1);
const visited = Array(K).fill(false);
let answer = Infinity;

// 순열을 통해 모든 회전에 대한 경우의 수 확인
function permutation(cur, depth, copyArr) {
    let copyArr2 = JSON.parse(JSON.stringify(copyArr));

    let [r, c, s] = operation[cur];
    let lt = [r - s - 1, c - s - 1]; // 왼쪽 위
    let rb = [r + s - 1, c + s - 1]; // 오른쪽 아래
    let rt = [lt[0], rb[1]]; // 오른쪽 위
    let lb = [rb[0], lt[1]]; // 왼쪽 아래

    // 회전 연산 수행
    while (true) {
        if (lt[0] > rb[0] || lt[1] > rb[1]) break;
        copyArr2 = rotate(lt, rb, rt, lb, copyArr2);
        lt[0]++;
        lt[1]++;
        rb[0]--;
        rb[1]--;
        rt = [lt[0], rb[1]];
        lb = [rb[0], lt[1]];
    }

    // 하나의 순열을 다 탐색했을 경우
    if (depth === K) answer = Math.min(answer, checkMin(copyArr2));

    for (let i = 0; i < K; i++) {
        if (!visited[i]) {
            visited[i] = true;
            permutation(i, depth + 1, copyArr2);
            visited[i] = false;
        }
    }
}

// 회전
function rotate(lt, rb, rt, lb, copyArr) {
    const copyArr2 = JSON.parse(JSON.stringify(copyArr));
    for (let i = lt[1] + 1; i <= rt[1]; i++) {
        copyArr2[lt[0]][i] = copyArr[lt[0]][i - 1];
    }
    for (let i = rt[0] + 1; i <= rb[0]; i++) {
        copyArr2[i][rt[1]] = copyArr[i - 1][rt[1]];
    }
    for (let i = rb[1] - 1; i >= lb[1]; i--) {
        copyArr2[rb[0]][i] = copyArr[rb[0]][i + 1];
    }
    for (let i = lb[0] - 1; i >= lt[0]; i--) {
        copyArr2[i][lb[1]] = copyArr[i + 1][lb[1]];
    }
    return copyArr2;
}

function checkMin(arr) {
    let min = Infinity;
    for (let row of arr) {
        min = Math.min(
            min,
            row.reduce((acc, cur) => (acc += cur))
        );
    }
    return min;
}

for (let i = 0; i < K; i++) {
    if (!visited[i]) {
        visited[i] = true;
        permutation(i, 1, copyArr);
        visited[i] = false;
    }
}

console.log(answer);

후기

사각형을 회전하는 부분을 구현하기가 좀처럼 쉽진 않았다.
매개변수로 전달되는 배열은 얕은 복사가 일어난다는 점을 신경써줘야 했다.
다만 배열을 깊은 복사 하는 부분이 수행 시간을 많이 잡아먹는 것 같다.

=============수정=============

코드 (개선)

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M, K] = input[0].split(' ').map(Number);
const arr = input.slice(1, 1 + N).map((low) => low.split(' ').map(Number));
const rcs = input.slice(1 + N).map((low) => low.split(' ').map(Number));
const visited = Array(K).fill(false);
let answer = Infinity;

function permutation(nums) {
    if (nums.length === K) {
        let copyArr = JSON.parse(JSON.stringify(arr));
        for (let i of nums) {
            let [r, c, s] = [...rcs[i]];
            rotate(r - 1, c - 1, s, copyArr);
        }
        getMin(copyArr);
        return;
    }
    for (let i = 0; i < K; i++) {
        if (!visited[i]) {
            visited[i] = true;
            permutation([...nums, i]);
            visited[i] = false;
        }
    }
}

function rotate(r, c, s, arr) {
    while (true) {
        let x = c - s;
        let y = r - s;
        if (s === 0) break;

        let temp = arr[y][x];
        while (y < r + s) {
            arr[y][x] = arr[++y][x];
        }
        while (x < c + s) {
            arr[y][x] = arr[y][++x];
        }
        while (y > r - s) {
            arr[y][x] = arr[--y][x];
        }
        while (x > c - s) {
            arr[y][x] = arr[y][--x];
        }
        arr[y][x + 1] = temp;
        s--;
    }
}

function getMin(arr) {
    for (let i = 0; i < N; i++) {
        answer = Math.min(
            answer,
            arr[i].reduce((acc, cur) => acc + cur, 0)
        );
    }
}

permutation([]);
console.log(answer);

이전 코드에서는 동작 속도를 늦추는 두 가지 문제점이 있었다.

순열을 한 번 수행할 때마다 사각형을 회전시키는 코드를 실행했다. 이러한 특성 때문에 회전시키기 전의 사각형에 대한 정보를 저장하기 위해서 배열을 깊은 복사를 해놔야 했다.
사각형을 시계방향으로 회전시키면 앞에 위치한 값이 덮어씌어지는 문제가 발생하기 때문에 원본 사각형을 하나 더 만들어놔야 했다. (지금 생각해보니 굳이 원본 사각형을 만들지 않고, 앞에 있는 값을 temp변수에 임시로 저장해 놓는 방법도 있었을 것 같다.)

개선된 코드에서는 위 두 문제점을 개선시켰다.

하나의 완전한 순열이 만들어졌을 때만 사각형을 회전 시킨다. 이로써 깊은 복사는 완전한 순열이 만들어졌을 때 한 번만 수행해주면 된다.
사각형을 반시계 방향으로 돌면서 시계 방향으로 도는 효과를 내준다. 사각형의 값의 움직임은 시계방향이 맞지만 코드의 동작 순서는 반시계 방향으로 진행시켜줌으로써 이 문제를 해결할 수 있고, 코드도 더 깔끔하게 수정했다.