• TOC {:toc}

이 글은 백준 온라인 저지의 17406번 문제를 자바스크립트(JavaScript)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2023.02.22

메모리 시간 코드 길이
16088 KB 288 ms 1495 B
단계 시작 시각 끝난 시각 걸린 시간
문제 이해 11:02:05 11:06:11
풀이 생각 11:06:13 11:18:49
코딩 1 11:19:00 12:15:13
코딩 2 12:18:29 12:57:28
디버깅 16:08:01 16:14:59 
const fs = require("fs");
const input = fs.readFileSync("./input-1.txt").toString().trim().split("\n");
// const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [NMK, ...lines] = input;
const [N, M, K] = NMK.split(" ").map((n) => parseInt(n));
const operation = lines.slice(N).map((line) => line.split(" ").map((n) => parseInt(n)));
const res = [];

function rotate(matrix, r, c, s) {
    const rotated = matrix.map((row) => [...row]);

    for (let k = 1; k <= s; k += 1) {
        for (let i = 0; i < 2 * k; i += 1) {
            rotated[r - k][c - k + i + 1] = matrix[r - k][c - k + i];
            rotated[r - k + i + 1][c + k] = matrix[r - k + i][c + k];
            rotated[r + k][c + k - i - 1] = matrix[r + k][c + k - i];
            rotated[r + k - i - 1][c - k] = matrix[r + k - i][c - k];
        }
    }
    return rotated;
}

function dfs(matrix, visited, count) {
    if (count === K) {
        // 각 행의 합을 구해서 그 중 최솟값을 res에 넣는 함수
        res.push(Math.min(...matrix.map((row) => row.reduce((acc, curr) => acc + curr, 0))));
    }
    for (let i = 0; i < K; i += 1) {
        if (!visited[i]) {
            const [r, c, s] = operation[i];
            const rotated = rotate(matrix, r - 1, c - 1, s);
            const newVisited = [...visited];
            newVisited[i] = true;

            dfs(rotated, newVisited, count + 1);
        }
    }
}

function main() {
    const matrix = lines.slice(0, N).map((line) => line.split(" ").map((n) => parseInt(n)));
    const visited = Array(K).fill(false);

    dfs(matrix, visited, 0);
    return Math.min(...res);
}

console.log(main());

아이디어 & 풀이

주어진 연산들을 조합해 진행한 결과값 중 최솟값을 출력한다.

  • 모든 경우의 연산을 진행해보려면 연산을 중복없이 한 개씩 선택해나가면 된다.
  • 중복을 관리하기 위해 visited를 이용한다.
    • i번째로 입력받은 연산의 수행여부가 visited[i]이다.
    • 기본적으로 flase로 초기화한 뒤 해당 연산을 진행하면 visited[i] 값을 true로 바꾼다.

즉, 입력받은 연산을 하나의 배열로 만들어(i.e. operation) 이를 순회하면서

  • visited[i]의 값이 false이면 해당 연산 값으로 회전 연산을 진행하고
  • count를 한 개 올려 해당 과정을 재귀적으로 반복한다.
  • 모든 연산을 거치면 (count 값이 연산의 개수와 같아지면) 회전 연산이 끝난 행렬의 값을 구한다.
  • 구한 값중 최솟값을 구해 출력한다.

회전 연산은 다음과 같이 구현한다.

  • 중점에서부터 x, y 축으로 각각 1, 2, …, s만큼 떨어진 정사각형을 각각 회전시키는 것이므로
  • 기존의 배열을 복사한 뒤
  • k = 1 부터 k <= s까지 반복적으로 각 사각형을 회전시킨다.
  • 사각형의 꼭지점부터 각 변의 이동경로에 맞춰 2 * s개의 원소를 이동시키면 된다.

디버그

  • 연산이 끝날 때만 최솟값을 비교해서 저장해야 하는데 매번 재귀 함수를 실행할 때마다 최솟값을 구해서 틀린 것 같다.
  • 최솟값을 비교해서 저장할 정확한 타이밍을 구하지 못해서 그냥 마지막에 계산한 최솟값을 모두 res에 넣은 뒤 그 중 최솟값을 출력했다.

피드백

  • 반복문에서 해당 시점에만 visited[i]의 값을 true로 바꿔서 dfs로 넘겨주고 반복할 때는 다시 기존의 visited를 사용해야 해서 고민하다가 기존의 visited를 복사해 사용했는데, visited[i]의 값을 true로 바꾼 뒤 dfs로 넘겨주고 다시 visited[i]의 값을 false로 돌려놓는 방법을 많이 쓰는 것 같다.