[Baekjoon] 18111: 마인크래프트 - (C3, S2) Brute Force

 

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

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

18111번: 마인크래프트

 

브루트포스 알고리즘으로, 정답률 24%가 보여주듯 어렵다. 땅의 각 칸중, 가장 작은 높이와 가장 큰 높이를 범위로 설정한다. 이 범위 내에서 모든 높이마다 해당 높이로 만들 때 시간을 계산하고 가장 작은 경우를 반환한다. 

 

class Minecraft
{
private:
    vector<vector<int>> map; // 땅
    int max_height_;         // 최대 높이. 초기값 INT_MAX
    int min_height_;         // 최소 높이. 초기값 INT_MIN

public:
    Minecraft(int n, int m);
    void setMap(int i, int j, int h);                      // 땅의 좌표별 높이 설정
    int getMapEle(int i, int j) const;                     // 땅의 좌표별 높이 반환
    pair<int, int> calculateWork(int target_height) const; // 특정 높이에서의 작업량 계산
    void setHeight();                                      // 최대/최소 높이 설정
    int getMaxHeight() const;                              // 최대 높이 반환
    int getMinHeight() const;                              // 최대 높이 반환
};

setHeight 함수는 min_height_과 max_height_을 계산한다. calulateWork 함수는 target_height에서 필요한 작업량을 반환하는데, 몇개의 블록을 제거하고 몇개의 블록을 추가해야 하는지 계산한다. 

 

void Minecraft::setHeight()
{
    for (const auto &row : map)
        for (const auto &h : row)
        {
            max_height_ = max(max_height_, h);
            min_height_ = min(min_height_, h);
        }
}

pair<int, int> Minecraft::calculateWork(int target_height) const
{
    int remove = 0, add = 0;

    for (const auto &row : map)
        for (const auto &h : row)
        {
            if (h > target_height)
                remove += h - target_height;
            else if (h < target_height)
                add += target_height - h;
        }
    return {remove, add};

map을 순회하면서, target_height보다 높으면 제거해야 할 블록의 개수(remove)를 추가한다. 작으면 추가해야 할 블록의 개수(add)를 추가한다.

 

class Player
{
private:
    const short MINING_TIME_ = 2; // 1번 작업 시간
    const short PUT_TIME_ = 1;    // 2번 작업 시간
    int block_;                   // 인벤토리의 블록 수
    int time_;                    // 작업에 걸리는 총 시간

public:
    Player(int b) : block_(b), time_(0) {};
    int getBlock() const;              // 인벤토리의 블록 수 반환
    int getTime() const;               // 작업 시간 반환
    void mineBlock(int count);         // 1번 작업
    void putBlock(int count);          // 2번 작업
    pair<int, int> work(Minecraft &m); // 평탄화된 높이과 작업 시간 반환
};

Player는 평탄화 작업을 수행한다. 

 

void Player::mineBlock(int count)
{
    block_ += count;
    time_ += count * MINING_TIME_;
}

void Player::putBlock(int count)
{

    block_ -= count;
    time_ += count * PUT_TIME_;
}

각 작업을 수행하는 함수는 블럭의 개수와 시간을 업데이트한다. 

 

pair<int, int> Player::work(Minecraft &m)
{
    int min_time = INT_MAX;
    int target_height = 0;

    for (int h = m.getMinHeight(); h <= m.getMaxHeight(); h++)
    {
        auto [remove, add] = m.calculateWork(h); // 최소 높이부터 최대 높이까지 brute force

        if (remove + block_ >= add)
        {
            int time = remove * MINING_TIME_ + add * PUT_TIME_;
            if (time < min_time || (time == min_time && h > target_height))
            { // 답이 여러개면 높이가 큰거
                min_time = time;
                target_height = h;
            }
        }
    }
    return {min_time, target_height};
}

map의 최소 높이와 최대 높이 사이를 순회하여 최소 시간과 높이를 확정한다. 

 

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, B;
    cin >> N >> M >> B;

    Minecraft mine(N, M);
    Player player(B);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            int h;
            cin >> h;
            mine.setMap(i, j, h);
        }

    mine.setHeight();
    pair<int, int> result = player.work(mine);
    cout << result.first << " " << result.second;

    return 0;
}

main에서는 땅의 각 값을 설정한 후, setHeight()함수를 호출해 높이를 계산한다. 그리고 work() 함수를 호출해 시간과 높이를 계산하고 출력한다. 

 

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

class Minecraft
{
private:
    vector<vector<int>> map; // 땅
    int max_height_;         // 최대 높이. 초기값 INT_MAX
    int min_height_;         // 최소 높이. 초기값 INT_MIN

public:
    Minecraft(int n, int m);
    void setMap(int i, int j, int h);                      // 땅의 좌표별 높이 설정
    int getMapEle(int i, int j) const;                     // 땅의 좌표별 높이 반환
    pair<int, int> calculateWork(int target_height) const; // 특정 높이에서의 작업량 계산
    void setHeight();                                      // 최대/최소 높이 설정
    int getMaxHeight() const;                              // 최대 높이 반환
    int getMinHeight() const;                              // 최대 높이 반환
};

Minecraft::Minecraft(int n, int m) : max_height_(INT_MIN), min_height_(INT_MAX)
{
    map.resize(n, vector<int>(m));
}

void Minecraft::setMap(int i, int j, int h)
{
    map[i][j] = h;
}

int Minecraft::getMapEle(int i, int j) const
{
    return map[i][j];
}

void Minecraft::setHeight()
{
    for (const auto &row : map)
        for (const auto &h : row)
        {
            max_height_ = max(max_height_, h);
            min_height_ = min(min_height_, h);
        }
}

int Minecraft::getMaxHeight() const
{
    return max_height_;
}

int Minecraft::getMinHeight() const
{
    return min_height_;
}

pair<int, int> Minecraft::calculateWork(int target_height) const
{
    int remove = 0, add = 0;

    for (const auto &row : map)
        for (const auto &h : row)
        {
            if (h > target_height)
                remove += h - target_height;
            else if (h < target_height)
                add += target_height - h;
        }
    return {remove, add};
}

class Player
{
private:
    const short MINING_TIME_ = 2; // 1번 작업 시간
    const short PUT_TIME_ = 1;    // 2번 작업 시간
    int block_;                   // 인벤토리의 블록 수
    int time_;                    // 작업에 걸리는 총 시간

public:
    Player(int b) : block_(b), time_(0) {};
    int getBlock() const;              // 인벤토리의 블록 수 반환
    int getTime() const;               // 작업 시간 반환
    void mineBlock(int count);         // 1번 작업
    void putBlock(int count);          // 2번 작업
    pair<int, int> work(Minecraft &m); // 평탄화된 높이과 작업 시간 반환
};

int Player::getBlock() const
{
    return block_;
}

int Player::getTime() const
{
    return time_;
}

void Player::mineBlock(int count)
{
    block_ += count;
    time_ += count * MINING_TIME_;
}

void Player::putBlock(int count)
{

    block_ -= count;
    time_ += count * PUT_TIME_;
}

pair<int, int> Player::work(Minecraft &m)
{
    int min_time = INT_MAX;
    int target_height = 0;

    for (int h = m.getMinHeight(); h <= m.getMaxHeight(); h++)
    {
        auto [remove, add] = m.calculateWork(h); // 최소 높이부터 최대 높이까지 brute force

        if (remove + block_ >= add)
        {
            int time = remove * MINING_TIME_ + add * PUT_TIME_;
            if (time < min_time || (time == min_time && h > target_height))
            { // 답이 여러개면 높이가 큰거
                min_time = time;
                target_height = h;
            }
        }
    }
    return {min_time, target_height};
}

int main()
{
    // freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, B;
    cin >> N >> M >> B;

    Minecraft mine(N, M);
    Player player(B);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            int h;
            cin >> h;
            mine.setMap(i, j, h);
        }

    mine.setHeight();
    pair<int, int> result = player.work(mine);
    cout << result.first << " " << result.second;

    return 0;
}