[알고리즘] - BOJ 2110 공유기 설치

• 이번 문제는 백준 온라인 저지 2110번 공유기 설치 문제입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

접근 방식

• 문제의 요구 조건에 따라 가능한 멀리 공유기를 떨어뜨려 설치해야 합니다. 그렇기 때문에 수직선 위에 존재하는 집들을 정렬한 뒤, 가장 앞에 있는 집 또는 가장 뒤에 있는 집은 반드시 공유기가 설치되어야 합니다. 그래야 가능한 멀리 공유기를 떨어뜨려 설치할 수 있기 때문입니다.
  • 이에 따라, 가장 앞에 있는 집에 공유기를 반드시 설치한다고 가정하고 문제에 접근했습니다.
• 공유기 사이의 최대 범위를 기준으로 해당 범위를 좁혀가며 조건을 만족하는 최대 범위를 파악하기 위해 이진탐색을 진행합니다.
  • 문제의 조건 중 x1, x2 … xn으로 표기되는 집들 사이의 간격이 최대 10억 단위까지 늘어날 수 있습니다. 그렇기 때문에 이러한 넓은 범위를 O(N^2) 시간복잡도로 순차 탐색할 경우 시간 초과가 날 확률이 높습니다.
• 앞선 접근 방식에 따라 첫 집을 기준점으로 잡고, 첫 집으로부터 가장 멀리 떨어진 마지막 집(리스트가 정렬되었다고 가정할 때)과 첫 집 사이의 거리를 end로, 집 사이의 간격 중 가장 좁은 간격을 1로 가정하고 이를 start로 설정하여 이진탐색을 진행했습니다.
  • 첫 집과 그 다음 집 사이의 간격을 start로 설정한다면 보다 효율적으로 초기에 이진탐색의 범위를 줄일 수 있다고 생각했으나, 첫 집 - 다음 집 사이의 간격보다 중간에 있는 집들 사이의 간격이 더 좁을 가능성이 있습니다.
  • 그렇기 때문에 위와 같이 첫 집과 다음 집 사이의 간격을 start로 잡을 경우 오류가 발생합니다. 따라서 여러 집들 사이의 간격 중 가장 좁은 간격을 찾아야 하지만 이를 찾기 위해선 모든 집들 사이의 간격을 탐색해야 하니, 배보다 배꼽이 더 커지는 상황이 발생합니다.
  • 그렇기 때문에 조금의 비효율을 감안하더라도 start를 1로 설정하여 탐색을 수행했습니다. 10억의 탐색 범위라 하여도 이진탐색 자체가 O(log N)으로 수행 가능하기 때문에 문제 풀이에는 지장을 주지 않습니다.

구현

# BOJ 2110, 공유기 설치
import sys

# 해당 간격으로 집집마다 공유기를 설치할 때, 해당 공유기의 개수를 모두 설치할 수 있는지 확인하는 함수
def install_wifi(gap, arr, wifi_num):
    cur_house = arr[0]
    cnt = 1
    # 첫 번째 집에 와이파이를 설치했다고 가정하고, 주어진 간격으로 wifi를 몇 개나 설치할 수 있을지 확인
    for house in arr:
        if house >= cur_house + gap:
            cnt += 1
            cur_house = house

    if cnt >= wifi_num:
        return True

    return False

input = sys.stdin.readline
n, c = map(int, input().rstrip().split())
home = [int(input().rstrip()) for _ in range(n)]

# 이진탐색을 위한 정렬
home.sort()

start, end = 1, home[-1] - home[0]
max_gap = 0
while start <= end:
    mid = (start + end) // 2

    if install_wifi(mid, home, c):
        # 해당 gap으로 wifi를 모두 설치할 수 있다면, 해당 결과를 저장한 뒤 gap을 넓혀서 탐색
        start = mid + 1
        max_gap = mid
    else:
        # 해당 gap으로 wifi를 모두 설치할 수 없다면, gap을 좁혀서 탐색
        end = mid - 1

print(max_gap)

• 이진탐색을 수행하면서 gap의 범위를 절반으로 반복적으로 줄여나갑니다.
• 이진탐색 수행 과정에서 mid(gap)을 설정한 뒤, 해당 gap으로 공유기를 집집마다 설치할 때 문제에서 요구한 공유기의 개수를 모두 설치할 수 있는지를 확인합니다. 이를 통해 만약 설치가 가능하다면 gap의 범위를 더 넓히며 탐색을 수행합니다. gap이 될 수 있는 수 중에서 최대의 수를 찾는 것이 문제의 조건입니다.
• 만약 해당 gap으로 공유기를 설치하였을 때 문제에서 요구한 공유기를 모두 설치할 수 없을 경우, 공유기를 다 설치할 수 있도록 하는 것이 우선이기 때문에 gap의 범위를 좁혀서 탐색을 수행합니다.

Lesson

사실 문제를 처음 푸는 과정에서 어떤식으로 접근해야 하는지 어려움을 많이 겪었습니다. 문제의 분류가 이진탐색임을 이해하지 못해 많이 헤매었습니다. 두 번째로 문제를 풀면서야 조금은 이해를 한 것 같은데, 반복적으로 학습하면서 이진탐색을 어떤식으로 활용하면 좋을지 더 공부해야겠습니다.