[Java] 백준 18111 마인크래프트 더 효율적으로 풀기

문제

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

목재를 충분히 모은 lvalue는 집을 짓기로 하였다.
하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.
lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다.

우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다.

우리는 다음과 같은 두 종류의 작업을 할 수 있다.
1. 좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
2. 인벤토리에서 블록 하나를 꺼내어 좌표 (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이다.

 

출력

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

 

 

예시

 

풀이

 

Brute Force 문제지만 재밌을 것 같아서 풀어보았다.

 

조금 단순해 보이는 문제이지만, 여러 조건이 까다로웠다.

1. 블럭을 파는 시간과 설치하는 시간이 다르다.

2. 판 블럭을 인벤토리에 넣어서 다시 사용할 수 있다.

3. 같은 시간이 걸리면 더 높은 높이를 출력한다.

4. 걸리는 시간과 높이를 모두 출력한다.

 

0. 성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static int n;
    public static int m;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st  = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());


        int[][] land = new int[n][m];

        int blocks = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                int block = Integer.parseInt(st.nextToken());
                land[i][j] = block;
                blocks += block;
            }
        }

        // 후보 추출
        int average = blocks / (n * m);
        blocks += b; //땅에 있는 블럭 + 갖고 있는 블럭 모두 합하기

        // maxHeight & minHeight 정하기
        int maxHeight = blocks / (n * m); //땅에 있는 블럭과 갖고 있는 블럭으로 쌓을 수 있는 최대 높이
        if (maxHeight > 256) { //최대 높이는 256
            maxHeight = 256;
        }
        int minHeight = 0;


        //평균으로부터 위로 쌓는 방향 검사
        int minTimeUpSide = Integer.MAX_VALUE;
        int currentHeightUpside = average; //평균부터 시작
        boolean isDone = false;
        while (!isDone) {
            if (currentHeightUpside > maxHeight) { //최대 높이를 넘었는지 검사
                break;
            }

            int currentTime = calTime(land, currentHeightUpside);  //걸리는 시간 검사
            if (currentTime <= minTimeUpSide) { // 만약 걸린 시간이 더 작다면 (=을 넣어서 같은 시간이어도 높이가 크다면 큰게 저장됨)
                minTimeUpSide = currentTime; //minTime에 저장
                currentHeightUpside++; //다음 높이 (위 방향)
            } else {
                isDone = true;
            }
        }
        currentHeightUpside--; // 높이 복구

        //평균으로부터 아래로 쌓는 방향 검사
        int minTimeDownSide = Integer.MAX_VALUE;
        int currentHeightDownside = average; //평균 부터 시작
        isDone = false;
        while (!isDone) {
            if (currentHeightDownside < minHeight) { //최소 높이를 넘었는지 검사
                break;
            }

            int currentTime = calTime(land, currentHeightDownside); //걸리는 시간 검사
            if (currentTime < minTimeDownSide) { //만약 걸린 시간이 더 작다면
                minTimeDownSide = currentTime; //minTime에 저장
                currentHeightDownside--; //다음 높이 (아래 방향)
            } else{
                isDone = true;
            }
        }
        currentHeightDownside++; //높이 복구

        if (minTimeUpSide <= minTimeDownSide) { //윗 방향의 시간이 더 짧다면 (=을 넣어서 더 높은 높이가 출력됨)
            System.out.println(minTimeUpSide + " " + currentHeightUpside );
        }else System.out.println(minTimeDownSide+ " " + currentHeightDownside); //아랫 방향의 시간이 더 짧다면
    }

    public static int calTime(int[][] land ,int height) {
        int time = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int diff = height - land[i][j];
                if ( diff >= 0) {
                    time += diff;
                } else time += -diff * 2;
            }
        }
        return time;
    }
}

1. 문제 풀이

Brute Force

혼자 풀어보고 나서 다른 사람들의 풀이를 보았는데,

거의 쌓인 블럭들의 최소와 최대 높이를 모두 검사하거나, 0칸부터 최대 높이까지 모두 검사하는게 대부분이었다.

 

시간이 가장 짧게 걸리는 높이라면, 현재 블럭들의 높이와 비슷하겠다 ~ 라는 생각으로,

 

나는 최대한 효율적으로 탐색해보기 위해 평균값을 도입해 보았다.

 

내 알고리즘은 이렇다.

1. 현재 땅에 쌓여있는 블럭들과, 내가 가지고 있는 블럭들을 모두 합한다. (설치할 수 있는 모든 블럭을 모은다.)

2. 모든 블럭들의 평균 값(=높이)을 구한다.

3. 평균 값부터 시작해서, 위로 쌓아가는 방식과 아래로 쌓아가는 방식을 모두 진행하면서, 해당 높이를 만드는데에 걸리는 시간을 구한다.

4. 위로 쌓아가는 방식 중 가장 시간이 짧은 높이와, 아래로 쌓아가는 방식 중 가장 시간이 짧은 높이를 구한다.

위로&아래로 쌓아가다가, 더이상 최소값이 나오지 않는다면 그만둔다. (블럭을 쌓거나 캐는데에 시간이 걸리므로, 더 이상의 높은 높이나 낮은 높이는 계산하지 않아도 최소값이 되지 않는다.)

5. 두 값 중 시간이 짧은 높이와 시간을 출력한다.

만약 같다면 위로 쌓아간 방식의 높이와 시간을 출력한다. (시간이 같다면 높이가 높은 시간을 출력)

 

여기서 최대 높이는 1번에서 구한 값 / N*M 값이다. 만들 수 있는 높이 중 최대 값이다.

최소 높이는 0이다.

 

조금 더 효율적인 것 같긴 하다.. ㅎㅎ

 

알고리즘 문제 중 Brute Force문제가 제일 재밌는 것 같다.

정해져 있지 않은 알고리즘 내에서 자유롭게 구현하는 매력이 있는 것 같다.