[BOJ][⚪2][백준#18111] 마인크래프트

문제 출처

BAEKJOON Online Judge #18111

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다. 목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다. lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다. 인벤토리에서 블록 하나를 꺼내어 좌표 (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이다.

출력

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

예제

예제 1

입력

3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

출력

2 0

예제 2

입력

3 4 1
64 64 64 64
64 64 64 64
64 64 64 63

출력

1 64

예제 3

입력

3 4 0
64 64 64 64
64 64 64 64
64 64 64 63

출력

22 63

My Sol

import sys
input = sys.stdin.readline

def dig(i):
    global B, main, time, Cnt
    if main[i-1] and main[i]:
        Cnt -= 1

    time += 2 * main[i]
    B += main[i]
    main[i-1] += main[i]
    main[i] = 0


def fill(i):
    global B, main, time, Cnt
    if main[i+1] and main[i]:
        Cnt -= 1

    time += 1 * main[i]
    B -= main[i]
    main[i+1] += main[i]
    main[i] = 0


# 입력
H, W, B = map(int, input().split())
arr = []
for _ in range(H):
    arr.extend(map(int, input().split()))

# main 배열
L = max(arr)
main = [0]*(L+1)
for a in arr:
    main[a] += 1

# Cnt 계산
Cnt = 0
for m in main:
    if m:
        Cnt += 1
time = 0


# 최소 최댓값 구하기
for i in range(L+1):
    if main[i]:
        front = i
        break
for i in range(L, -1, -1):
    if main[i]:
        back = i
        break

while Cnt > 1:
    if (B >= main[front]) and (main[front] <= main[back]*2):
        fill(front)
        front += 1
    else:
        dig(back)
        back -= 1

print(time, back)

입력 처리 및 코드 진행 방식

카운팅 정렬의 인덱스 누적 방식을 사용하면 효율적으로 풀 수 있는 문제였다. 우선 입력을 2차원으로 받는 것이 아니라, 1차원적 리스트로 입력을 처리하고, 이 중 가장 큰 수까지 인덱스로 취할 수 있도록 max+1만큼 0이 반복되는 arr를 초기화해준다. 이후 각 값을 인덱스로 하여 더해주는, 즉, 높이를 인덱스로 하여 특정 높이(인덱스)에 쌓인 것이 몇 개나 되는지를 체크하는 main 배열을 따로 지정해준다. 만약 땅의 높이가 최대 256이 아니라 더 높았다면 인덱스가 너무 커져 할 수 없는 방식이지만, 256개는 충분히 가능할 것이라고 판단했다.

최소높이 front / 최대높이 back / 높이 개수 Cnt 계산

이후 front, back으로 가장 낮은 곳의 높이와 가장 높은 곳의 높이를 찾아준다. arr에 대하여 min(), max()를 사용해도 되지만, 중간에 끊고 싶어서 알고리즘으로 정의해주었다. 이후 front와 end가 만나는, 즉 main 배열의 값들을 이동시켜주면 한 인덱스로 모으게 되면 이때의 높이와 이때까지 소요된 시간을 출력하는 것인데, 최초 main 함수가 완성되었을 때, 항목을 가지는 인덱스의 개수를 Cnt로 세어주었기 때문에 while문의 종료 조건은 Cnt가 1이 되는 때이다. 즉, Cnt가 1이 되면 파거나 채우는 이 과정을 종료하는 것이다.

한층 빼거나 넣기 : while 반복

파고, 빼는 것은 함수를 사용해주었다. 어차피 평탄화를 하는 것이므로 하나씩 하는 것이 아니라 한 번에 높이를 올리거나 낮춰야 하는데, 우선 시간이 가장 적게 소요되는 방식이어야 하므로, main[front]가 main[back]*2 보다 작으면 채워주어야 한다.

이때 2가지를 고려해야 하는데, 같은 시간이면 높이가 높을수록 좋으므로 main[front]와 main[back]*2이 같을 때에는 front를 높여주는 fill() 함수를 실행해야 한다. 그런데 더더욱 중요한 조건은, 되도록 fill() 함수를 쓰려 하겠지만, 인벤토리의 블록의 개수 B가 front에 채워야하는 블록의 개수 main[front]보다 적으면 층을 높일 수 없으므로 꼼짝없이 dig() 함수로 최고층을 까내려야 한다. 이를 조건으로 잘 처리해준다.

dig() / fill() 함수

우선 dig나 fill를 할 때 채우거나 까내리는 높이와 이미 같은 높이의 블럭이 있다면 main 배열에서 두 인덱스가 하나로 합쳐지는 것이므로 Cnt를 하나 줄여준다. 이후 dig와 fill에서 해당 층도 같이 평탄화 과정에 참여할 것이다. 이후 단순히 이동하려는 쪽으로 인덱스의 값을 합쳐주고 원래 인덱스의 값은 0으로 만드는 과정이다.

결과

맞았습니다!!