[Baekjoon / Python] 18111. 마인크래프트

출처

18111번 - 마인크래프트

알고리즘 분류

• 구현
• 브루트포스 알고리즘

문제

풀이

import sys

N, M, B = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
ans_height, ans_time = 0, int(1e10)
max_val = 0
for i in range(len(board)):
    for j in range(len(board[0])):
        max_val = max(max_val, board[i][j])
        
for h in range(max_val, -1, -1):
    total_time, block = 0, 0
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] > h:
                total_time += (board[i][j] - h) * 2
                block += board[i][j] - h
            else:
                total_time += h - board[i][j]
                block -= h - board[i][j] 
    
    if B + block < 0:
        continue
    
    if total_time <= ans_time:
        ans_time = total_time
        ans_height = h

print(ans_time, ans_height)

초기에 작성한 코드는 위와 같습니다. 블록을 제거하는 데 소요되는 시간이 블럭을 꺼내는 시간보다 많이 걸리므로, 초기 땅 높이의 최댓값을 기준으로 거꾸로 순회하여 완전탐색을 통해 최소 시간을 계산하였습니다.
해당 알고리즘의 시간복잡도는 $O(N^2)$이고, 최악의 경우에는 256 x 500 x 500 = 64,000,000번의 연산을 필요로 하므로, 문제의 제한 시간인 1초 안에 넉넉하게 통과할 것이라 생각했지만, 시간 초과가 발생하였습니다.
원인 분석을 위해 구글링을 해보니, python은 인터프리터 언어이기 때문에 연산 횟수에 따른 소요 시간이 타 언어에 비해 굉장히 높은 것으로 확인되었습니다.

So 1 billion * 9 opcodes / 112.37 seconds = about 80,092,551 opcodes per second. It’s like we’re in the 1980s!
출처 : https://www.stephanboyer.com/post/38/counting-to-a-billion

2013년에 작성된 글이기 때문에 현 시점 CPU의 연산량은 더 증가했을테지만, 파이썬은 일반적인 컴파일 언어에 비해서 20배 이상 느리기 때문에 문제 해결에 있어서 더 효율적인 알고리즘이나 자료구조를 선택해야 합니다.

많은 고민 끝에, 딕셔너리를 이용하여 코드를 수정하였습니다. 이전에는 동일한 높이에 대해서도 일일이 탐색하여 연산을 수행했지만, 딕셔너리를 통해 높이와 개수를 key, value 형식으로 저장하여 일괄적인 연산이 이루어지도록 개선하였습니다.
따라서 연산의 횟수는 256 x 딕셔너리의 길이로, 시간복잡도 또한 $O(N)$으로 획기적으로 개선되었습니다.

import sys

N, M, B = map(int, sys.stdin.readline().split())
height_dic = {}
for i in range(N):
    board = list(map(int, sys.stdin.readline().split()))
    for height in board:
        if height in height_dic.keys(): 
            height_dic[height] += 1
        else:
            height_dic[height] = 1

ans_height, ans_time = 0, int(1e10)
for h in range(257):
    total_time, block = 0, 0
    for key in height_dic.keys():
        if key > h:
            total_time += (key - h) * height_dic[key] * 2
            block += (key - h) * height_dic[key]
        else:
            total_time += (h - key) * height_dic[key]
            block -= (h - key) * height_dic[key]
   
    if B + block < 0:
        continue
    
    if total_time <= ans_time:
        ans_time = total_time
        ans_height = h
        
print(ans_time, ans_height)

시간 복잡도

$O(N)$

실행 결과