[백준 실버 2] 18111번: 마인크래프트

문제

https://www.acmicpc.net/problem/18111

 

 

풀이

• 마인크래프트의 땅 고르기 작업을 한다. 땅 고르기란, 범위 내의 블록 높이를 같은 상태로 만드는 작업이다.
• 땅 고르기 범위는 N X M 크기이다.
• 하나의 블록을 캐면 2초가 걸리고, 그 블록이 인벤토리에 저장된다.
• 하나의 블록을 설치하면 1초가 걸리고, 인벤토리에서 꺼낸 블록을 사용한다. 인벤토리에 블록이 없다면 설치할 수  없다.
• 땅의 높이는 최소 0, 최대 256이다. 블록은 최대 64,000,000개가 주어질 수 있고, 맵의 크기는 최대 500 X 500이다.
• 맵 전체의 땅을 고르는데 걸리는 최소 시간을 구해야 한다. 만약 시간이 같다면 땅의 높이가 더 높은 경우를 출력한다.

 

주어진 맵의 크기가 크지 않아 브루트포스 알고리즘을 사용해 해결할 수 있는 문제이다.

단, 몇 가지 유의해야 하는 부분이 있다.

1. 캐낸 블록을 다시 설치하는 데 사용할 수 있다는 점
2. 최소 시간인 경우가 여러 개라면, 그중에 땅의 높이가 더 높은 경우를 선택한다는 점

이 두 가지를 생각하며 문제에 접근하였다.

 

땅을 고르기 위해서는 먼저 땅의 높이를 지정할 필요가 있다. 땅의 높이를 기준으로 낮은 부분은 블록을 채워 넣고, 높은 부분은 블록을 캐서 제거해야 한다.

땅의 높이는 현재 맵에서 제일 높은 블록과 제일 낮은 블록의 높이만 고려하면 된다. 이 범위를 넘어가는 높이는 낭비일 뿐이다.

 

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int lvalue[][] = new int[N][M];
boolean visited[][] = new boolean[N][M];

int maxHigh = Integer.MIN_VALUE;
int minHigh = Integer.MAX_VALUE;

for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < M; j++) {
        int input = Integer.parseInt(st.nextToken());
        lvalue[i][j] = input;

        maxHigh = Math.max(maxHigh, input);
        minHigh = Math.min(minHigh, input);
    }
}

 

2차원 배열 lvalue에 입력받은 블록의 높이를 저장함과 동시에, maxHigh와 minHigh를 선언하여 최저 높이와 최고 높이를 찾는다. 이 범위의 높이만 고려하며 땅 고르기를 시작한다.

 

현재 블록 개수와 걸린 시간을 파악하기 위해 itemB와 sec을 선언하였다.

이때, 기준 높이보다 낮은 블록을 채워 넣을 때, 현재 블록이 부족할 수 있다. 그렇기 때문에 높은 블록을 캐며 최대한 블록을 확보해야 한다.

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {

        int targetHigh = lvalue[i][j];

        if (targetHigh == standardHigh) {
            visited[i][j] = true;
            continue;
        } else if (targetHigh > standardHigh) {
            sec += 2 * (targetHigh - standardHigh);
            itemB += targetHigh - standardHigh;
            visited[i][j] = true;
        }

    }
}

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        if (visited[i][j])
            continue;

        int targetHigh = lvalue[i][j];

        if (targetHigh < standardHigh) {
            sec += (standardHigh - targetHigh);
            itemB -= standardHigh - targetHigh;
        }

    }
}

 

블록을 하나 캐는데 2초, 설치하는데 1초가 걸리기 때문에, 각각 상호작용한 블록 수만큼 sec에 더해준다. 또, 현재 가진 블록 숫자도 판단한다.

 

해당 높이의 모든 땅 고르기 계산이 끝난 경우, 방문한 맵을 다시 초기화한다.

그리고 itemB가 음수라면, 블록이 모자랐다는 뜻이므로 이 경우는 고려하지 않고 넘어간다.

 

계산 결과 걸린 시간이 현재까지 최소 시간보다 적다면, 최소 시간과 해당 높이를 갈아치운다. 이때, 같은 시간이면 높이가 높은 쪽을 선택한다는 조건을 위해, 시간이 같은 경우도 판별한다. standardHigh가 점점 커지기 때문에, 같은 시간의 경우 자연스럽게 높은 쪽이 선택된다.

 

 

 

전체 코드 (Java)

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

public class Main {

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

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int lvalue[][] = new int[N][M];
		boolean visited[][] = new boolean[N][M];

		int maxHigh = Integer.MIN_VALUE;
		int minHigh = Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				int input = Integer.parseInt(st.nextToken());
				lvalue[i][j] = input;

				maxHigh = Math.max(maxHigh, input);
				minHigh = Math.min(minHigh, input);
			}
		}

		int minSec = Integer.MAX_VALUE;
		int high = 0;

		for (int standardHigh = minHigh; standardHigh <= maxHigh; standardHigh++) {
			int itemB = B;
			int sec = 0;

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {

					int targetHigh = lvalue[i][j];

					if (targetHigh == standardHigh) {
						visited[i][j] = true;
						continue;
					} else if (targetHigh > standardHigh) {
						sec += 2 * (targetHigh - standardHigh);
						itemB += targetHigh - standardHigh;
						visited[i][j] = true;
					}

				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (visited[i][j])
						continue;

					int targetHigh = lvalue[i][j];

					if (targetHigh < standardHigh) {
						sec += (standardHigh - targetHigh);
						itemB -= standardHigh - targetHigh;
					}

				}
			}

			for (boolean[] b : visited) {
				Arrays.fill(b, false);
			}

			if (itemB < 0)
				break;


			if (minSec >= sec) {
				minSec = sec;
				high = standardHigh;
			}
		}


		System.out.println(minSec + " " + high);

	}

}

 

 

후기

실수가 많아 푸는데 정말 오래 걸렸다.

실수 1. 블록을 캐거나 설치할 때, 블록의 개수를 ++, --로 계산하였다.

실수 2. 블록 설치와 블록 캐기를 한 반복문 안에서 처리하다 보니, 블록을 캘 수 있음에도 인벤토리의 블록이 부족하여 채울 수 없는 경우가 발생하였다. 블록을 먼저 모두 캐고, 그다음 설치하는 방향으로 문제를 해결하였다.

실수 3. 제일 크게 고생한 부분이다.

if (itemB < 0)
    break;

if (sec == 0) {
    minSec = 0;
    continue;
}

if (minSec >= sec) {
    minSec = sec;
    high = standardHigh;
}

 

땅 고르기를 끝내고 조건들을 비교할 때 범한 실수이다. sec이 0인 경우 minSec을 0으로 초기화하고 반복문을 빠져나가는 코드를 작성하였다. 당시 무슨 생각으로 이런 멍청한 실수를 저질렀는지 모르겠지만 추측해 보자면, 땅 고르기가 이뤄지지 않은 경우를 판별하기 위해 쓴 것 같다. 그러나 잘 생각해 보면, 땅 고르기가 이뤄지지 않은 경우는 크게 두 가지이다. 이미 땅이 고른 상태이거나, 블록이 부족하여 땅 고르기를 못한 경우일 것이다. 하지만 후자는 이미 itemB이 0보다 작은지 판별하였고, 땅이 이미 고른 경우엔 후에 이뤄질 조건문에서도 충분히 판별 가능하다. high에 높이를 대입할 기회마저 박탈하여 후에 경곗값과 관련된 반례에서 많이 실패하였다.

 

이러한 실수를 방지하기 위해서는 누더기 같이 코드를 수정해가는 것보단 코드를 타이핑하기 전에 확실하게 의사코드를 작성하는 습관으로 해결해야 한다고 생각한다.