실생활 예시로 이해하는 스윕 라인 알고리즘 (Sweep line Algorithm)

Sweep은 “쓸다”라는 의미를 가지고있는데, 스윕 라인 알고리즘은 빗자루로 먼지를 쓸어내듯이 특정 방향을 따라 스위핑하면서 점 또는 선을 확인하며 답을 찾아가는 알고리즘이다. 선분의 교차 여부, 구간 겹, 점의 분포등을 계산할 수 있기때문에 주로 시/공간의 겹침, 자원할당, 스케쥴링 문제를 다룰때 해결할 수 있는다. 나도 마찬가지로 회의실 예약 관련 Tool을 만들다 접하게되었다.

 

 

스윕 라인 알고리즘의 문제 해결과정은 대부분 이렇다:

출처: Wikipedia

1. 모든 데이터를 특정 기준에따라 정렬한다.
2. 스위핑 라인을 이동시키며 데이터를 하나씩 처리한다.

 

내 경우 회의실이 비는 시간을 파악하기 위해서 사용했는데, 이를 단순화한 예시로 스윕 라인 알고리즘을 알아보자.

 

3개의 회의실이 있고, 이미 예약된 회의가 있다.

이미 예약된 회의가 다음과 같을때, 2시 반에는 몇 개의 회의실을 사용할 수 있을까?

total_rooms = 3
meetings = [[1, 3], [2, 4], [3, 5]] # 1시~3시, 2시~4시, 3시~5시 예약

check_time = 2.5
# 2시 반에는 몇개의 회의실을 사용할 수 있는가?

 

 

먼저, 회의실 예약(meetings)를 시작시간과 종료 시간으로 나누어 배열로 만든다.

events = []
for start, end in meetings:
    events.append(('start', start))
    events.append(('end', end))

 

 

그리고 시간순으로 정렬한다.

events.sort(key=lambda x: x[1])
# [('start', 1), ('start', 2), ('end', 3), ('start', 3), ('end', 4), ('end', 5)]

 

 

이제 한 방향으로만 확인하면서 현재 사용중인 회의실 수를 체크할 수 있다.

active_rooms = 0  # 현재 사용 중인 회의실 수

for event_type, time in events:
    # 확인할 시간이 현재 이벤트 시간보다 크면 멈춘다.
    if time > check_time:
        break
    if event_type == 'start':
        active_rooms += 1
    else: 
        active_rooms -= 1

 

 

check_time에 사용중인 회의실을 전체 회의실에서 빼면 특정 시간에 빈 회의실 수를 얻을 수 있다.

available_rooms = total_rooms - active_rooms
return available_rooms

 

 

이해를 돕기 위해 ‘start’, ‘end’를 쪼갰지만, 이벤트를 만들때 회의실 수 변화를 함께 처리하면 더 간단하다.

def find_available_rooms(meetings, total_rooms, check_time):
    events = []
    for start, end in meetings:
        events.append((start, 1)) # 회의 시작
        events.append((end, -1)) # 회의 끝

    events.sort()

    active_rooms = 0 

    for time, change in events:
        if time > check_time:
            break
        active_rooms += change

    available_rooms = total_rooms - active_rooms
    return available_rooms