스위핑 기법 (Python)

스위핑이란?

스위핑(Sweeping) 기법이란 말 그대로 어느 한 쪽에서부터 휩쓸고 지나가는 알고리즘을 의미한다.

즉, 주어진 요소를 특정 기준에 따라 정렬한 후 순차적으로 처리하는 기법이 바로 스위핑이다.

 

정의에서도 알 수 있듯이, 스위핑 기법은 굉장히 단순하면서도 범용적으로 사용된다.

같은 스위핑 기법을 활용하는 문제더라도 사용해야 하는 자료 구조나 구현 방식은 천차만별이다.

따라서 스위핑을 적용하는 경우 대부분 다른 자료 구조나 알고리즘에 대한 이해와 적용이 필요하다.

 

대표적인 문제들(BOJ)

[2170] 선 긋기

2170번: 선 긋기

 

스위핑 기법을 적용하는 대표적인 문제이다.

 

수직선에 그려진 여러 선들의 총 길이를 구하는 문제로, 겹치는 부분이 중복으로 더해지지 않도록 유의해야 한다.

선들을 오름차순으로 정렬한 후, 직전 선과 겹치면 해당 선을 늘려주고, 아니면 그냥 더해주는 방식으로 처리하면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
arr = [tuple(map(int, input().split())) for _ in range(n)]

arr.sort()
answer = arr[0][1] - arr[0][0]
last = arr[0][1]

for left, right in arr[1:]:
    if left <= last < right:
        answer += right - last
        last = right
    elif left >= last:
        answer += right - left
        last = right

print(answer)

 

[2846] 수상 택시

2836번: 수상 택시

 

상근이는 어쩌피 목적지까지 이동해야기 때문에, 사람들을 역방향으로 태워줘야 하는 경우만 고려하면 된다.

여기까지 생각했다면, 역방향으로 이동하는 경우만 모아 선긋기 문제처럼 해결하면 된다.

 

[20930] 우주 정거장

20930번: 우주 정거장

 

이동 가능한 정거장은 서로 x좌표가 겹치거나 y좌표가 겹친다.

따라서 정거장들을 각각 x좌표, y좌표를 기준으로 정렬한 후 각각에 대해 스위핑을 진행해주면 된다.

이 때, 겹치는 정거장 처리는 분리 집합(Union-Find)를 이용하면 쉽게 처리할 수 있다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200001)

def find(x):
    if x != disjoint[x]:
        disjoint[x] = find(disjoint[x])
    return disjoint[x]


def union(x, y):
    x = find(x)
    y = find(y)
    disjoint[max(x, y)] = min(x, y)


def is_same(x, y):
    return find(x - 1) == find(y - 1)


n, q = map(int, input().split())
x_arr = []
y_arr = []

for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    x_arr.append((*sorted([x1, x2]), i))
    y_arr.append((*sorted([y1, y2]), i))

disjoint = [i for i in range(n)]
x_arr.sort()
y_arr.sort()

lr, lt = x_arr[0][1:]
for i in range(n):
    l, r, t = x_arr[i]
    
    if l <= lr:
        lr = max(lr, r)
        union(lt, t)
    else:
        lr = r
        lt = t

lr, lt = y_arr[0][1:]
for i in range(n):
    l, r, t = y_arr[i]
    
    if l <= lr:
        lr = max(lr, r)
        union(lt, t)
    else:
        lr = r
        lt = t

for _ in range(q):
    print(int(is_same(*map(int, input().split()))))

 

[2672] 여러 직사각형의 전체 면적 구하기

2672번: 여러 직사각형의 전체 면적 구하기

각 직사각형이 시작되는 부분과 끝나는 부분의 x좌표와 y좌표들을 기록해두자.

해당 기록들을 x좌표를 기준으로 정렬한 후, 구간을 순회하면서 해당 구간에 존재하는 사각형의 넓이를 더해나가면 된다.

 

구간에 존재하는 사각형의 넓이는 좌표를 하나씩 체크해나가도 되고, y좌표를 기준으로 다시 선긋기 문제처럼 길이를 구해도 된다.

해당 길이(y좌표 길이)에 구간의 너비(x좌표 길이)를 곱하면 해당 구간의 넓이가 된다.

 

import sys
input = sys.stdin.readline

START, FINISH = 0, 1
n = int(input())
arr = []

for _ in range(n):
    x, y, w, h = map(lambda x: int(float(x) * 10) , input().split())
    arr.append((x, y, y + h, START))
    arr.append((x + w, y, y + h, FINISH))

arr.sort()

answer = 0
ys = [(arr[0][1], arr[0][2])]
last_x = arr[0][0]

for i in range(1, n * 2):
    x, y_low, y_high, lt = arr[i]
    
    y = 0
    if ys:
        ys.sort()
        low, high = ys[0]
        for j in range(1, len(ys)):
            l, h = ys[j]
            if l <= high: high = max(high, h)
            else:
                y += high - low
                low, high = l, h
        y += high - low
    
    answer += (x - last_x) * y
    
    if lt == START:
        ys.append((y_low, y_high))
    else:
        ys.remove((y_low, y_high))
    
    last_x = x

if answer % 100 == 0:
    print(answer // 100)
else:
    print(f'{answer / 100:.2f}')

 

입력은 10을 곱해 소수 연산으로 인한 오차를 제거하였다.

정수로 나타낼 수 있는 경우에는 정수부만 출력한다는 조건에 유의하자.

 

자매품으로 $N$이 커 세그먼트 트리 등의 자료 구조를 활용해야 하는 [3392] 화성 지도, 좌표의 범위가 커 좌표 압축을 해줘야 하는 [7626] 직사각형 문제가 있다.

 

[5419] 북서풍

5419번: 북서풍

먼저 좌표의 범위가 크므로 좌표 압축을 해준다.

이후 x 좌표에 대해 오름차순(같다면 y 좌표에 대해 내림차순)으로 정렬해준 후, 좌측부터 스위핑하며 지금까지의 점들 중 자기보다 상단에 있는 섬의 수를 세주면 된다.

 

이 때 섬의 수를 Naive하게 구해주면 총 시간복잡도가 $O(N^2)$이 되어 시간 초과가 난다.

값의 변화가 가능하면서도 빠르게 구간 합을 관리할 수 있는 자료 구조(세그먼트 트리, 제곱근 분할법, 펜윅 트리 등)을 이용한 최적화가 필요하다.