[Java] BOJ 18111 마인크래프트

문제 

문제 링크 https://www.acmicpc.net/problem/18111

• 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다.
• 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.
• lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.
  1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
  2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.
• 1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다.
• ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.
• 단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다.
• 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.
• 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.
• 첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)
• 둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다.
• (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.
• 첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

아이디어

• 땅의 높이가 0부터 256까지라고 하였으므로 0부터 256까지 for문을 돈다.
• for문을 돌면서 시간초와 남은 블럭 수를 계산할 변수를 항상 초기화해주며, 해당 땅의 높이가 기준 높이보다 높으면 해당 높이만큼 블럭 수를 더해주고 그 높이만큼 2를 곱해서 시간초에 더해준다.
• 만약 해당 땅의 높이가 기준 높이보다 낮으면 해당 높이만큼 블럭 수를 빼주고 높이만큼 시간초를 더해준다.
• 땅을 다 돌고 난 후, 남은 블럭의 수가 0보다 크거나 같고 계산된 초가 현재 결과값보다 작거나 같다면 결과초와 땅 높이를 갱신해준다.  

겪은 시행착오

• 처음에 DFS로 풀려다가... 실패해서 3중 for문으로 풀게 되었다... 일단 완탐으로 풀어놓고 다른 방법을 생각해보든 해야겠다...!

우선은 구현부터...!

코드

import java.io.*;
import java.util.*;

public class BOJ18111 {

    static int N;
    static int M;
    static int B;
    static int ground[][];
    static int result;
    static int result2;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 열
        N = Integer.parseInt(st.nextToken());
        // 행
        M = Integer.parseInt(st.nextToken());
        // 땅의 개수
        B = Integer.parseInt(st.nextToken());

        // 땅의 높이를 저장할 배열
        ground = new int[N][M];
        // 초를 저장할 변수
        result = Integer.MAX_VALUE;
        // 땅의 높이를 저장할 변수
        result2 = 0;

        // 배열에 값 저장
        for(int i = 0; i < N; i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++){
                int n = Integer.parseInt(st2.nextToken());

                ground[i][j] = n;
            }
        }

        for(int h = 0; h <= 256; h++){
            // 시간초를 계산할 변수
            int s = 0;
            // 남은 블럭 수
            int b = B;

            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    if(ground[i][j] > h){
                        int height = ground[i][j] - h;

                        // 기준 땅보다 현재 땅 높이가 높으므로 남은 땅 수에 더해줌
                        b = b + height;

                        // 블럭을 제거하여 인벤토리에 넣었으므로 넣은 블록 수 * 2초
                        s = s + 2*height;
                    }
                    else if(ground[i][j] < h){
                        int height = h - ground[i][j];

                        // 기준 땅보다 현재 땅 높이가 낮으므로 남은 땅 수에 빼줌
                        b = b - height;

                        // 블럭을 좌표에 넣어서 넣은 블록 수 * 1초
                        s = s + height;
                    }
                }
            }

            // 블럭수가 0개보다 크고 계산된 초가 결과값보다 작거나 같다면
            // 결과초와 땅 높이를 갱신
            if(b >= 0 && s <= result){
                result = s;
                result2 = h;
            }
        }

        System.out.println(result + " " + result2);
    }
}