BOJ 18111 마인크래프트

By kuper0201

Published in 알고리즘

2021-03-05

2 min read

문제

입력

풀이

문제

BOJ 18111 마인크래프트 바로 가기

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 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 × 10^7)

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

풀이

땅 고르기 작업이 완료되기 까지의 최소 시간과 높이를 구하는 문제이다.

해당 문제는 가능한 높이 전체의 시간을 비교하는 전수 검사(Brute Force) 알고리즘을 이용해 해결 할 수 있다.

높이가 0층일 때 걸리는 시간
높이가 1층일 때 걸리는 시간
높이가 2층일 때 걸리는 시간
...
높이가 256층일 때 걸리는 시간(땅의 높이는 256블록을 초과 할 수 없다)

을 모두 비교하여 최소 시간과 그 때의 높이를 출력하면 된다.

하지만 항상 256층을 모두 돌아보기에는 비효율적이라는 생각이 든다.

위와 같은 입력이 주어졌을 때 집터 바깥에서 블록을 가져올 수 없다.라는 제약 조건으로 인해 해당 입력에서는 최대 층수가 1층으로 어떻게 해도 평평한 2층 이상의 땅을 만들 수 없기 때문에 2층 이상의 경우를 고려할 필요가 없어진다.

하지만 0층 ~ 256층 까지 모두 돌아보는 방법은 2층 ~ 256층 만큼 의미 없는 반복이 계속 될 것이다.

이러한 의미 없는 반복을 줄이기 위해서는 현재 가지고 있는 블록(캘 수 있는 블록 + 인벤토리에 있는 블록)을 이용해 최대로 쌓을 수 있는 높이가 몇 층인지 확인해 해당 높이만큼만 반복하면 된다.

(캘 수 있는 블록 + 인벤토리에 있는 블록) / (땅의 가로 * 땅의 세로) 공식(평균 공식)을 이용하면 현재 가지고 있는 블록을 이용해 쌓을 수 있는 최대 높이를 구할 수 있다.

이후 0층 ~ 256층 까지가 아닌 0층 ~ 최대 높이 까지의 시간만 비교하면 필요한 최소의 반복만으로 해당 문제를 풀어낼 수 있다.

코드 보기(Java)

import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");

        // 가로, 세로, 인벤토리 입력
        int M = Integer.parseInt(str[0]);
        int N = Integer.parseInt(str[1]);
        int B = Integer.parseInt(str[2]);

        // 땅 높이 입력
        int map[][] = new int[M][N];
        long sum = 0;
        for (int i = 0; i < M; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                sum += map[i][j];
            }
        }

        // (캘 수 있는 블록 + 가진 블록) / (가로 * 세로) 공식으로 최대 높이를 구한다
        int maxHeight = (int)((sum + B) / (M * N));
        int minTime = Integer.MAX_VALUE, targetHeight = 0;

        // 최대 높이까지 반복하며 시간을 비교한다
        for (int i = 0; i <= maxHeight; i++) {
            int time = 0;

            for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    if (map[j][k] > i) time += (map[j][k] - i) * 2;
                    else if (map[j][k] < i) time += i - map[j][k];
                }
            }

            // 답이 여러 개 있을 경우 가장 높은 층을 저장하기 위해 >= 조건 사용
            if (minTime >= time) {
                minTime = time;
                targetHeight = i;
            }
        }

        System.out.println(minTime + " " + targetHeight);
    }
}

코드 보기(C++)

#include <iostream>
using namespace std;

int main() {
    // 가로, 세로, 인벤토리 입력
    int M, N, B;
    cin >> M >> N >> B;
    
    // 땅 높이 입력
    int map[M][N];
    int sum = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            sum += map[i][j];
        }
    }
    
    // (캘 수 있는 블록 + 가진 블록) / (가로 * 세로) 공식으로 최대 높이를 구한다
    int maxHeight = (int)((sum + B) / (M * N));
    int minTime = 2147483647, targetHeight = 0;
    
    // 최대 높이까지 반복하며 시간을 비교한다
    for (int i = 0; i <= maxHeight; i++) {
        int time = 0;
        
        for (int j = 0; j < M; j++) {
            for (int k = 0; k < N; k++) {
                if (map[j][k] > i) time += (map[j][k] - i) * 2;
                else if (map[j][k] < i) time += i - map[j][k];
            }
        }
        
        // 답이 여러 개 있을 경우 가장 높은 층을 저장하기 위해 >= 조건 사용
        if (minTime >= time) {
            minTime = time;
            targetHeight = i;
        }
    }
    
    cout << minTime << " " << targetHeight;
    return 0;
}

코드 보기(Kotlin)

fun main(args: Array<String>) {
    // 가로, 세로, 인벤토리 입력
    var str = readLine()!!.split(' ')
    var M = str[0].toInt()
    var N = str[1].toInt()
    var B = str[2].toInt()
    
    // 땅 높이 입력
    var sum = 0
    var map = Array(M,{IntArray(N,{0})})
    for(i in 0 until M) {
        str = readLine()!!.split(' ')
        for(j in 0 until N) {
            map[i][j] = str[j].toInt()
            sum += map[i][j]
        }
    }
    
    // (캘 수 있는 블록 + 가진 블록) / (가로 * 세로) 공식으로 최대 높이를 구한다
    var maxHeight = (sum + B) / (M * N)
    var minTime = Int.MAX_VALUE
    var targetHeight = 0

    // 최대 높이까지 반복하며 시간을 비교한다
    for(i in 0..maxHeight) {
        var time = 0
            
        for(j in 0 until M) {
            for(k in 0 until N) {
                if (map[j][k] > i) time += (map[j][k] - i) * 2
                else if (map[j][k] < i) time += i - map[j][k]
            }
        }

        // 답이 여러 개 있을 경우 가장 높은 층을 저장하기 위해 >= 조건 사용
        if (minTime >= time) {
            minTime = time
            targetHeight = i
        }
    }
        
    println("$minTime $targetHeight")
}

코드 보기(Python)

def main():
    # 가로, 세로, 인벤토리 입력
    M, N, B = map(int, input().split(' '))
    arr = [[0 for j in range(N)] for i in range(M)]
    
    # 땅 높이 입력
    sum = 0
    for i in range(M):
        str = input().split(' ')
        for j in range(N):
            arr[i][j] = int(str[j])
            sum = sum + arr[i][j]
    
    # (캘 수 있는 블록 + 가진 블록) / (가로 * 세로) 공식으로 최대 높이를 구한다
    maxHeight = (sum + B) // (M * N)
    minTime = 2147483647
    targetHeight = 0
    
    # 최대 높이까지 반복하며 시간을 비교한다
    for i in range(maxHeight + 1):
        time = 0
        for j in range(M):
            for k in range(N):
                if arr[j][k] > i:
                    time = time + (arr[j][k] - i) * 2
                elif arr[j][k] < i:
                    time = time + i - arr[j][k]
                    
        # 답이 여러 개 있을 경우 가장 높은 층을 저장하기 위해 >= 조건 사용
        if minTime >= time:
            minTime = time
            targetHeight = i
    
    print(minTime, end=' ')
    print(targetHeight)
    
if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    // 가로, 세로, 인벤토리 입력
    var str = readLine()!.split(separator: " ")
    var M = Int(str[0])!
    var N = Int(str[1])!
    var B = Int(str[2])!
    
    
    // 땅 높이 입력
    var sum = 0
    var map = Array(repeating: Array(repeating: 0, count: N), count: M)
    for i in 0..<M {
        str = readLine()!.split(separator: " ")
        for j in 0..<N {
            map[i][j] = Int(str[j])!
            sum += map[i][j]
        }
    }
    
    // (캘 수 있는 블록 + 가진 블록) / (가로 * 세로) 공식으로 최대 높이를 구한다
    var maxHeight = (sum + B) / (M * N)
    var minTime = Int.max
    var targetHeight = 0
    
    // 최대 높이까지 반복하며 시간을 비교한다
    for i in 0...maxHeight {
        var time = 0
        
        for j in 0..<M {
            for k in 0..<N {
                if map[j][k] > i {
                    time += (map[j][k] - i) * 2
                } else if map[j][k] < i {
                    time += i - map[j][k]
                }
            }
        }
        
        // 답이 여러 개 있을 경우 가장 높은 층을 저장하기 위해 >= 조건 사용
        if minTime >= time {
            minTime = time
            targetHeight = i
        }
    }
    
    print(minTime, targetHeight)
}

main()