[백준 18111번] 마인크래프트 with Java

guswls·2024년 4월 22일

백준 브루트포스

알고리즘

목록 보기

4/39

문제

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

코드

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

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[][] map = new int[N][M];

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

		System.out.println(solve(N, M, B, map));

	}

	static Result solve(int N, int M, int B, int[][] map) {

		// 1. 맵의 최대 높이와 최소 높이 구하기
		int max = Integer.MIN_VALUE;
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				max = Math.max(max, map[i][j]);
				min = Math.min(min, map[i][j]);
			}
		}

		PriorityQueue<Result> pq = new PriorityQueue<Result>();
		for (int i = min; i <= max; i++) {
			int time = 0;
			int block = B;
			int diff = 0;
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < M; k++) {
					// 1. i보다 맵이 낮은 경우, 블록을 쌓아야 함.
					if (map[j][k] < i) {
						diff = i - map[j][k];
						time += diff;
						block -= diff;
					}
					// 2. i보다 맵이 높은 경우 맵을 깎아야 함, 즉 블록을 지워야함
					else if (map[j][k] > i) {
						diff = map[j][k] - i;
						time += 2 * diff;
						block += diff;
					}
				}
			}

			if (block >= 0) {
				//i가 곧 height를 의미함.
				pq.add(new Result(time, i));
				break;
			}

		}
		return pq.poll();
	}

	static class Result implements Comparable<Result> {
		int time;
		int height;

		Result(int time, int height) {
			this.time = time;
			this.height = height;
		}

		
		@Override
		public int compareTo(Result o) {
			//시간이 같은 경우, 높이가 높은 경우가 우선순위가 높게
			if (this.time == o.time) {
				return Integer.compare(o.height, this.height);
			}

			// 시간이 다르면, 시간이 가장 짧은 경우의 우선순위를 높게
			return Integer.compare(this.time, o.time);
		}

		@Override
		public String toString() {
			return time + " " + height;
		}
	}
}

문제 이해

2차원 배열 내부의 값을 모두 같게 만드는 경우 중에, 그 소요시간이 제일 짧게 걸리는 경우에 대한 시간과 같아진 값을 출력하는 문제이다.
요소에 값을 더할 때는 더해진 값만큼의 시간이 걸리고, 값을 뺄 떄는 뺀 값의 2배만큼 시간이 걸린다.
만약 답이 여러 개인 경우에는 높이가 가장 높은 경우가 정답이 된다.

풀이 방법

문제에서 나온대로, 1) 블록을 제거해서 인벤토리에 넣는 동작, 2) 인벤토리에서 블록을 꺼내서 놓는 동작 두가지를 할 수 있다.
이떄 블록을 놓는 동작은 인벤토리에 블록이 있는 경우에만 진행할 수 있다.
고려해야할 점은 현재는 인벤토리에 블록이 없어도 그 다음 블록을 제거해서 인벤토리에 넣는다면 블록이 생길 수 있다는 것이다.
다음과 같은 상황을 가정하자.
- 이중 for문을 통해 2차원 배열을 접근한다.
- 예를 들어 [0, 1]시점에는 블록을 못 놓을 수 있더라도, [0, 2]에서 블록을 캔다면 [0, 1]시점은 블록을 놓을 수 있다.
따라서 현재 시점에서 인벤토리 블록의 개수를 따지는 것은 무의미하고, 특정 높이로 맵을 평평하게 만든 후에 블록이 0 이상인 경우를 유효하게 판단하도록 해야한다.
즉 브루트포스로 문제를 해결해야 한다.
브루트포스를 수행할 하한은 맵의 최소값, 상한은 맵의 최대값이다. 그 이외의 경우에 대해선 생각할 필요가 없다.
브루트포스를 통해 구해진 결과값은 문제의 조건에 맞도록 Result객체에 compareTo를 구현한 후, priorityQueue에 넣도록 하였다.
모든 동작이 끝난 후에, pq에서 꺼낸 값이 답이 된다.

핵심 포인트

단순히 O(N*M), 즉 이중 for문만 사용해서는 문제를 해결할 수 없다.
min ~ max 범위에서 유효한 모든 결과를 구하고, 그중에 가장 작은 시간을 갖는 결과를 답으로 도출하면 된다.

보완할 점 / 느낀 점

dp와 더불어 브루트포스도 익숙하지 않았다. min ~ max범위에서 만들어지는 결과를 다뤄야한다는 아이디어를 떠올리지 못해 풀이를 찾아봤다.
추가적으로 순서를 보존할 필요가 없기 때문에 pq는 이 문제에서 오버스펙인 느낌이 있는 것 같다. 단순히 현재 도출된 값과 이전 값을 비교하는 로직만 추가해도 충분히 해결할 수 있어보인다.
브루트포스 문제도 많이 풀어봐야겠다.