[18111번] 마인크래프트 Minecraft

구현, 브루투포스 알고리즘, 211103

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.

인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.

1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

입력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

예제 입력 1

Plain Text
복사

예제 출력 1

Plain Text
복사

맨 오른쪽 아래의 블록을 제거하면 모두 높이가 0으로 고른 상태가 된다. 따라서 블럭을 한 번 제거하는 시간 2초가 소요된다.

예제 입력 2

Plain Text
복사

예제 출력 2

Plain Text
복사

인벤토리에 블록이 하나 있기 때문에, 맨 오른쪽 아래에 블록을 하나 채우면 된다.

예제 입력 3

Plain Text
복사

예제 출력 3

Plain Text
복사

인벤토리가 비어 있기 때문에, 맨 오른쪽 아래를 제외한 모든 좌표에서 블록을 하나씩 제거해야 한다.

My solution

가로 N, 세로 M이 주어진다.

B는 인벤토리에 남아있는 블록의 개수. 즉, 이게 1개 이상 있을 때 부족한 높이를 채울 수가 있다면 채우는 것이 좋다. 왜냐면 뜯어서 인벤토리에 넣는 것보다 인벤토리에 있는 블록을 꺼내서 높이를 채우는 것이 더 빠른 작업이다. ( 2초 < 1초 )

Math.max(map)으로 key를 구할 수는 없다. reduce 사용

// map의 가장 큰 값으로 비교를 해서 그 키와 값을 같이 반환해주는 reduce 활용법
const max = [...map.entries()].reduce((a, e) => (e[1] > a[1] ? e : a));
JavaScript
복사

Map에 높이들을 담아서 가장 많이 나온 높이(Map의 max value와 key)로 모든 높이를 빼준다음 그 값이 양수면 그만큼 빼주면서 시간을 재고, 그 값이 음수면 그만큼 블록이 필요하므로 인벤토리에 블록이 있어야 했다. 근데 음수이면서 인벤토리에 블록이 없다면? 이 방식으로 계산하면 틀릴 것이라는 걸 예상할 수 있었다.

브루투포스 알고리즘이라 해서 이중for문이나 삼중 for문을 떠올렸는데 어떻게 계산해야할지 떠오르지 않았다.

참고 : https://cotak.tistory.com/94

일단 N, M, B를 할당하고 각 높이의 배열 g를 만들어 준다.(나중에 틀렸던 부분이 여기서 문자열 숫자가 들어왔다는 것이다. 즉, 매번 map(v⇒parseInt(v))를 해주는 것을 잊지 않도록 하자.)

[N, M, B] = input[0].split(" ").map((v) => parseInt(v));
    input.shift();
    g = input.map((v) => v.split(" ").map((v) => parseInt(v)));
JavaScript
복사

평탄화하는 함수를 만들어준다. 이 함수에서는 시간을 0으로 잡고 모든 높이들을 방문하면서 전달받은 높이와 같다면 무시하고 더 크다면 time에 그 차이만큼 *2로 넣어주고(걸리는 시간), 더 작다면 그 차이만큼 *1로 넣어준다. 이렇게 걸린 시간을 구한 뒤 [time, h]를 반환시킨다.

function flatten(h) {
    let time = 0;
    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            if (g[i][j] === h) continue;
            else if (g[i][j] > h) time += 2 * (g[i][j] - h);
            else time += h - g[i][j];
        }
    }
    return [time, h];
}
JavaScript
복사

이 평탄화함수는 모든 높이의 경우의 수에 실행된다.

result 배열은 [ 걸린 시간, 블록의 높이 ]를 넣어주기 위해 걸린 시간을 매우 큰 수로 넣어둔다.

let result = [Number.MAX_SAFE_INTEGER, 0];
let _sum = B;

for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
        _sum += g[i][j];
    }
}
JavaScript
복사

결과적으로 _sum 에는 B(인벤토리 블록)에 모든 블록의 높이를 더한 것이 누적되게 된다. 근데 이 블록들을 전부 다 합쳐서 N*M에 뿌려준다면 최대 높이가 몇까지 가능한지 알아야 for문으로 모든 높이의 경우의 수를 돌 수 있다. 따라서 아래와 같이 _max를 계산해주는 것이다.

let _max = Math.min(257, Math.floor(_sum / (N * M)) + 1);
JavaScript
복사

땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

라고 했기 때문이다. 최대 높이는 256보다 커질 수는 없다. for문에서는 0 ~ 256이 최대 범위이므로 <로 비교연산하는 것을 고려해서 257을 넣어주었다.

이제 h(높이)를 0부터 _max만큼 돌면서 그 가능한 높이의 경우의 수를 모두 전달해서 확인해본다. 위의 평탄화함수에 전달해보면 그 전달받은 h별로 걸리는 시간과 높이가 반환된다.

for (let h = 0; h < _max; h++) {
    [time, height] = flatten(h);
    if (time <= result[0]) {
        result[0] = time;
        if (height > result[1]) result[1] = height;
    }
}
JavaScript
복사

만약 그 시간이 result[0] (맨처음에는 매우 큰수)보다 같거나 작으면 이 시간으로 교체된다.

또, 그 시간이 같거나 더 작은 상황에서 그 높이가 result[1] (맨처음에는 0)보다 더 크다면 그 높이로 교체된다.

답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

모든 높이의 경우의 수를 돌아서 완성된 result가 답이 된다.

소스코드

function solution(i) {
    const input = i.toString().trim().split("\n");
    [N, M, B] = input[0].split(" ").map((v) => parseInt(v));
    input.shift();
    g = input.map((v) => v.split(" ").map((v) => parseInt(v)));

    function flatten(h) {
        let time = 0;
        for (let i = 0; i < N; i++) {
            for (let j = 0; j < M; j++) {
                if (g[i][j] === h) continue;
                else if (g[i][j] > h) time += 2 * (g[i][j] - h);
                else time += h - g[i][j];
            }
        }
        return [time, h];
    }

    let result = [Number.MAX_SAFE_INTEGER, 0];
    let _sum = B;

    for (let i = 0; i < N; i++) {
        for (let j = 0; j < M; j++) {
            _sum += g[i][j];
        }
    }

    let _max = Math.min(257, Math.floor(_sum / (N * M)) + 1);

    for (let h = 0; h < _max; h++) {
        [time, height] = flatten(h);
        if (time <= result[0]) {
            result[0] = time;
            if (height > result[1]) result[1] = height;
        }
    }
    console.log("result", result.join(" "));

    return result.join(" ");
}

test("solution", () => {
    //     expect(
    //         solution(`3 4 99
    // 0 0 0 0
    // 0 0 0 0
    // 0 0 0 1`)
    //     ).toStrictEqual("2 0");
    //     expect(
    //         solution(`3 4 1
    // 64 64 64 64
    // 64 64 64 64
    // 64 64 64 63`)
    //     ).toStrictEqual(`1 64`);
    expect(
        solution(`3 4 0
64 64 64 64
64 64 64 64
64 64 64 63`)
    ).toStrictEqual("22 63");
});
JavaScript
복사