라인 스위핑(Line Sweeping)은 평면 상의 어떤 선이나 세그먼트를 수평 방향으로 스캔하면서 문제를 해결하는 알고리즘 기법입니다. 일반적으로 두 점 사이의 거리나 겹치는 부분을 찾는 문제에서 사용됩니다. 라인 스위핑은 시간 복잡도를 줄이고 여러 문제를 효율적으로 해결할 수 있는 강력한 방법 중 하나입니다.

라인 스위핑의 주요 특징:

1. 수평 스캔: 수평 방향으로 선이나 세그먼트를 스캔하며 문제를 해결합니다.
2. 이벤트 포인트: 스캔 중에 발생하는 이벤트 포인트를 관리하고 처리합니다. 이벤트 포인트는 선이나 세그먼트의 시작과 끝점을 의미합니다.
3. 정렬: 이벤트 포인트를 정렬하여 처리 순서를 관리합니다.
4. 상태 관리: 스캔 중에 현재 상태를 관리하면서 문제를 해결합니다.

라인 스위핑의 활용 예시:

• 좌표 압축: 좌표의 범위가 큰 경우, 중복되지 않는 좌표로 압축하는데 라인 스위핑을 사용할 수 있습니다.
• 사각형 합집합 계산: 다수의 사각형이 주어졌을 때, 합집합된 영역의 넓이를 계산하는 문제에서 라인 스위핑을 사용할 수 있습니다.
• 중복된 구간 검사: 다수의 구간이 주어졌을 때, 중복된 부분을 검사하는 문제에서 라인 스위핑을 사용할 수 있습니다.

파이썬 코드를 통해 라인 스위핑을 예시로 살펴보겠습니다. 다음은 다수의 사각형의 넓이를 합친 총 넓이를 계산하는 라인 스위핑 코드입니다.

class Rectangle:
    def __init__(self, x1, y1, x2, y2):
        self.x1, self.y1, self.x2, self.y2 = x1, y1, x2, y2

def union_area(rectangles):
    events = []
    for rect in rectangles:
        events.append((rect.x1, rect.y1, 1))  # 직사각형 시작 이벤트
        events.append((rect.x2, rect.y1, -1))  # 직사각형 끝 이벤트

    events.sort()  # 이벤트 포인트 정렬
    active = []
    total_area = 0
    prev_x = events[0][0]

    for x, y, status in events:
        total_width = 0
        for i in range(len(active) - 1):
            total_width += active[i + 1] - active[i]

        total_area += total_width * (x - prev_x)
        if status == 1:
            active.append(y)
            active.sort()
        else:
            active.remove(y)

        prev_x = x

    return total_area

# 사각형들의 좌표 (x1, y1, x2, y2)
rectangles = [Rectangle(1, 1, 3, 3), Rectangle(2, 2, 4, 4), Rectangle(3, 1, 5, 2)]
total_area = union_area(rectangles)
print("총 넓이:", total_area)

이 코드는 다수의 사각형의 넓이를 합친 총 넓이를 계산하는 라인 스위핑 예시입니다. 이벤트 포인트를 정렬하고 스캔하면서 활성화된 사각형의 높이를 관리하여 넓이를 계산합니다.