[백준 1725] 히스토그램(세그먼트 트리)

문제 출처 : https://www.acmicpc.net/problem/1725

1725번: 히스토그램

히스토그램은 다양한 풀이 방법으로 유명한 문제 입니다. 스택, 분할정복, 세그먼트 트리로 풀 수 있습니다. 여기서는 세그먼트 트리의 다양한 응용에 대해 배우기 위해 세그먼트 트리로 푸는 방법을 알아보겠습니다.

문제 이해하기

문제 풀이를 위한 개념은 이렇습니다. 아래와 같은 히스토그램이 있습니다.

처음부터 끝까지를 모두 포함하는 직사각형은 가장 낮은 높이의 직사각형 입니다. 높이가 가장 낮은 항목이 아니라면 전체를 밑변으로 할 수 없습니다.

밑변이 7이고 높이는 1이기 때문에 전체를 밑변으로 하는 작사각형의 넓이는 7입니다. 이제 제일 낮은 높이를 기준으로 양쪽을 나눕니다. 높이가 1인 부분이 두 군데가 있지만 어느쪽으로 해도 상관 없습니다. 낮은 높이 중 2번째에 있는 1의 높이를 기준으로 나눠 보겠습니다.

왼쪽은 넓이가 2, 오른쪽은 넓이가 5 입니다. 왼쪽은 더 이상 나눌 수 없기 때문에 그대로 두고, 오른쪽을 가장 낮은 높이 기준으로 나누어 양쪽의 넓이를 구해 줍니다.

왼쪽 사각형의 넓이는 8이고, 오른쪽의 사각형 넓이는 6 입니다. 기존 가장 큰 넓이가 7이였는데 더 큰 넓이 8이 등장 했으니 가장 큰 넓이를 8로 변경합니다.

양쪽의 직사각형의 가장 낮은 높이를 기준으로 양 옆의 가장 낮은 높이로 넓이를 구해줍니다. 3번 높이의 왼쪽은 없기 때문에 오른쪽만 넓이를 확인합니다. 5이기 때문에 최대 넓이가 될 수 없습니다. 6번 높이 역시 왼쪽은 없기 때문에 오른쪽만 확인합니다. 3이기 때문에 최대 넓이가 될 수 없습니다.

따라서 위 히스토그램의 최대 넓이는 8임을 알 수 있습니다. 이것으로 최대 넓이를 구할 수 있었고 지금 최대 넓이를 구한 방법으로 알고리즘을 이해해 보겠습니다.

알고리즘 이해하기

1. 전체 범위에서 가장 낮은 높이를 구합니다.
2. 전체 넓이를 밑변으로 하는 넓이를 구해줍니다.
3. 1번에서 구한 가장 낮은 높이의 인덱스를 기준으로 왼쪽과 오른쪽의 가장 낮은 높이를 구합니다.
4. 왼쪽의 넓이, 오른쪽의 넓이를 구해 가장 넓은 넓이로 변경합니다.
5. 3번의 높이를 기준으로 양쪽을 나누어 넓이를 계속해서 구해줍니다.

이와 같은 알고리즘으로 이해할 수 있습니다. 우리는 범위를 바꿔가며 최대 넓이를 구해줍니다.

세그먼트 트리의 활용

여기서 세그먼트 트리가 어디서 쓰이는지 확인 하셨나요? 바로 범위의 최소값을 구하는데 사용되었습니다. 기억해야 하는 점은 최소값을 가지는 인덱스를 알아야 하는 것입니다. 높이를 통해 넓이를 구하기는 하지만 해당 인덱스를 기준으로 양쪽으로 나누기 때문에 최소값을 가지는 인덱스를 알아야 합니다.

코드 작성하기

그럼 문제를 같이 풀어보도록 하겠습니다. 기본적인 세그먼트 트리의 사용법은 여기를 확인하시기 바랍니다.

입력 받기

import sys
sys.setrecursionlimit(10 ** 5)

N = int(input())

arr = []
for i in range(N):
    arr.append(int(input()))

세그먼트 트리가 재귀 형태를 가지고 있기 때문에 재귀 함수가 돌 수 있도록 재귀의 허용치를 늘려 줍니다. 다음으로 히스토그램을 가로 칸의 개수를 입력 받습니다. 다음으로 N개의 히스토그램 높이를 입력 받습니다.

초기화 하기

다음으로 히스토그램을 초기화 하겠습니다.

tree = [0] * (4 * N)
def init(node, start, end):
    if start == end:
        tree[node] = (arr[start], start)
        return
            
    mid = (start + end) // 2
    init(2 * node, start, mid)
    init(2 * node + 1, mid + 1, end)
    tree[node] = min(tree[2 * node], tree[2 * node + 1])
    
init(1, 0, N-1)

최소 높이와 해당 인덱스를 모두 알아야 하기 때문에 둘 다 저장하였습니다.이 때 높이를 앞에 써주었기 때문에 min 함수를 사용했을 때 높이를 기준으로 낮은 값을 찾게 됩니다.

범위의 낮은 높이 찾기

def query(node, start, end, left, right):
    if right < start or end < left:
        return (1e9, 1e9)
    if left <= start and end <= right:
        return tree[node]
    
    mid = (start + end) // 2
    q1 = query(2 * node, start, mid, left, right)
    q2 = query(2 * node + 1, mid + 1, end, left, right)

    return min(q1, q2)

구하려는 범위의 가장 낮은 높이를 찾는 query 함수 입니다. 범위를 벗어났을 때 최대값을 리턴하여 포함되지 않도록 하였습니다.

범위의 넓이 구하기

def get_area(left, right):
    minHeight, minIdx = query(1, 0, N - 1, left, right)

    area = (right - left + 1) * minHeight

    if left < minIdx:
        val = get_area(left, minIdx - 1)
        area = max(area, val)

    if minIdx < right:
        val = get_area(minIdx + 1, right)
        area = max(area, val)
    return area

print(get_area(0, N-1))

범위의 넓이를 구하는 함수 입니다. query를 통해 가장 낮은 높이를 구합니다. 그 높이로 범위를 모두 포함하는 직사각형의 넓이를 구해줍니다. 다음으로 가장 낮은 높이의 인덱스를 기준으로 양 옆에 더 큰 넓이가 있는지 확인합니다.

전체 코드

그럼 전체 코드를 확인해 보겠습니다.

import sys
sys.setrecursionlimit(10 ** 5)

N = int(input())

arr = []
for i in range(N):
    arr.append(int(input()))

tree = [0] * (4 * N)
def init(node, start, end):
    if start == end:
        tree[node] = (arr[start], start)
        return
            
    mid = (start + end) // 2
    init(2 * node, start, mid)
    init(2 * node + 1, mid + 1, end)
    tree[node] = min(tree[2 * node], tree[2 * node + 1])
    
init(1, 0, N-1)

def query(node, start, end, left, right):
    if right < start or end < left:
        return (1e9, 1e9)
    if left <= start and end <= right:
        return tree[node]
    
    mid = (start + end) // 2
    q1 = query(2 * node, start, mid, left, right)
    q2 = query(2 * node + 1, mid + 1, end, left, right)

    return min(q1, q2)

def get_area(left, right):
    minHeight, minIdx = query(1, 0, N - 1, left, right)

    area = (right - left + 1) * minHeight

    if left < minIdx:
        val = get_area(left, minIdx - 1)
        area = max(area, val)

    if minIdx < right:
        val = get_area(minIdx + 1, right)
        area = max(area, val)
    return area

print(get_area(0, N-1))