[BOJ] 18111번 마인크래프트

[BOJ] 18111번 마인크래프트 문제

굉장히 어려웠던 브루트 포스(brute force) 문제였다.

애초에 이 문제가 브루트 포스라고 감이 오는 사람이 몇이나 있을까 싶기도 하다. 제한시간이 단 1초인 데다가, 최악의 경우 $ 25,000 \times 257 $가지의 경우를 다 둘러봐야 한다. 이 조건만으로 브루트 포스라고 판단하기엔 정말이지 힘들다.

파이썬에서는 대략적으로 1초에 1천만 개의 경우 정도까지가 브루트 포스로 풀 수 있는 최대 경우로 여겨진다. 다행히 이 문제는 $ 25,000 \times 257 = 6,425,000 $이므로 1천만보다는 적으니 브루트 포스로도 풀릴 수 있다. 덤으로 경우의 수가 매우 크다면 기존 파이썬으로는 시간 초과가 날 가능성이 높아서 반드시 Pypy3으로 제출해야 한다.

일단 브루트 포스라는 태그가 있는 걸 보고 들어왔다 해도 구현에서 굉장히 까다로움을 느끼게 된다. 브루트 포스의 핵심은 "어떻게 모든 과정을 돌릴 것인가?" 다. 하지만 이 문제는 난이도에 맞게 그 과정을 어떻게 돌릴지에 대해서 까다로움이 매우 높다. 마치 체스판 다시 칠하기를 처음 봤을 때 "이걸 어떻게 풀어?" 하는 느낌이다.

실제로 본인도 이 문제는 여러 블로그들을 통해 공부하고 풀었다. 사실 이렇게 공부하고 풀어도 여간 쉽진 않다.

---

이 문제의 핵심은 브루트 포스이고, 모든 상태를 둘러봐야 한다는 점이다. 모든 상태를 어떻게 둘러보는 것인가가 핵심이다.

그 방법은 바로 모든 바닥에서 0 ~ 256층으로 평탄화할 때 걸리는 시간을 구하는 것이다. 그렇기에 입력은 격자로 주어졌지만, 굳이 2차원 배열로 저장할 필요 없이 1차원으로 저장해도 무방함을 깨닫게 된다. 이를 함수로 나타내면 아래와 같고, extend 함수가 1차원으로 저장시켜주는 역할을 해준다.

def input_block(n):
    block_list = list()
    for _ in range(n):
        block_list.extend(list(map(int, sys.stdin.readline().rstrip().split())))

    return block_list

 

또한 아무리 블록을 파내도 그 층을 못 만드는 경우도 있기 때문에 이런 예외 상황을 적절히 걸러주는 것이 중요하다. 예제 3이 그 예다.

---

import sys

def input_block(n):
    block_list = list()
    for _ in range(n):
        block_list.extend(list(map(int, sys.stdin.readline().rstrip().split())))

    return block_list

if __name__ == '__main__':
    N, M, B = map(int, sys.stdin.readline().rstrip().split())
    mc_block = input_block(N)
    min_time, max_height = sys.maxsize, -1
    # min_height, max_height = min(mc_block), max(mc_block)
    
    for now_height in range(257):
    # for now_height in range(min_height, max_height + 1):
        stacked_block, dug_block = 0, 0
        for i in range(N*M):
            if mc_block[i] < now_height:
                stacked_block += now_height - mc_block[i]
            elif mc_block[i] > now_height:
                dug_block += mc_block[i] - now_height
            else:
                continue

        if stacked_block > dug_block + B:
            continue

        now_time = 2*dug_block + stacked_block
        if now_time <= min_time:
            min_time, max_height = now_time, now_height

    print(min_time, max_height)

 

모든 $ N \times M $의 바닥을 0 ~ 256층으로 평탄화하는 모든 경우를 구하는 경우를 상정해보자.

각 $ N \times M $의 바닥과 만들려고 하는 층의 차이를 구해서, 만약 파내려 가야 한다면(즉, 현재 만들려는 층보다 현 바닥의 층이 높다면) 파내려 가야 하는 블록 변수에 그 차이를 더하고, 반대로 쌓아야 한다면(즉, 현재 만들려는 층보다 현 바닥의 층이 낮다면) 쌓아야 하는 블록 변수에 그 차이를 더한다.

그리고 쌓아야 하는 블록 변수와 파내려 가야 하는 블록 변수 + 기존에 주어진 변수 B를 비교한다. 만약 전자가 크다면 블록이 부족하기 때문에 뒤에 있을 시간&평탄화 층 갱신을 하면 안 되고, 후자가 크다면 그때 시간&평탄화 층 갱신을 해준다. 지문에서 하나 팔 때 2초, 쌓을 때 1초라고 했으므로 시간 구하는 것은 어렵지 않다. 만약 그 시간이 현 최소 시간보다 작다면 현재 시간과 해당 평탄화 층을 갱신한다.

---

이 문제는 재밌게도 평탄화 층수의 최적화가 가능하다. 항상 0 ~ 256층으로 평탄화 검사를 할 필요가 없다. 입력으로 들어온 블록의 최솟값과 최댓값 사이의 값만 돌려도 충분하다!

생각해보면 이유를 알 수 있는데, 최소 블록 값보다 적어지면 더 파내기만 해야 하기 때문에 시간이 더 오래 걸리는 것은 너무나도 자명하며, 최대 블록 값보다 크다면 인벤토리에 있을 블록이 없거나 너무 많기 때문에 할 필요가 없다.

최소 블록 값은 파내는 행동의 시간이 2초이기에 이해가 빠르게 될 것이다. 최대 블록 값의 문장이 이해가 어려울 수 있는데, 이게 무슨 말인가 하면 최대 블록 값보다 큰 층으로 평탄화를 한다면 파내려 갈 블록이 없기 때문에 전적으로 변수 B에 의존하게 된다. B가 적으면 당연히 그 이상으로 갈 필요도 없고, B가 많다면 이는 적어도 최대 블록 값과 같거나 적은 층으로 평탄화가 가능하다는 의미다. 그래서 최대 블록 값보다 큰 층으로 평탄화를 할 필요가 없다.

작성한 코드에 주석 처리된 부분이 바로 입력으로 들어온 블록의 최솟값과 최댓값을 구하고, 그것을 평탄화 for문에 집어넣은 것이다. 실제로 평탄화 층수 최적화를 거친 결과가 더 빠르다.

평탄화 층 최적화 전(아래)과 후(위)