스윕 라인 알고리즘(Sweep Line Algorithm)

정렬을 사용하여 문제를 푸는 기법중 하나인 스윕 라인 알고리즘이다.

정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링 하는 방법

주로 O(N^2)의 시간복잡도를 갖는 방법으로 해결이 불가능하거나, DP를 사용하기에 메모이제이션 해야하는 데이터의 크기가 너무 클때 고려한다.

정렬 후 로직을 처리하므로 O(NlogN)의 시간 복잡도를 가진다.

예제

BOJ 2170 선긋기

https://www.acmicpc.net/problem/2170

내 생각

선을 겹쳐서 긋는 것에 대해서는 차이가 없기 때문에 좌표 위치만 확인하면 된다.

선이 어디서 시작하는지가 중요하기 때문에 x좌표를 기준으로 정렬을 진행한다.

이후 처음에 0번째의 left , right를 x와 y좌표를 담아두고, 반복하면서 다음 좌표의 y좌표가 기존의 left 보다 작다면 이는 연결되어 있는 녀석이라고 판단한다.

이 경우가 아니라면 연결되어 있지 않은 선분이라 판단하고, 연결되어 있던 정보를 계산한 후 새로운 x,y 좌표를 담아 다시 선분을 시작한다.

코드

class BOJ2170 {
    fun solve(){
        val n = readLine()!!.toInt() // 선 그은 횟수 , 최대 1,000,000임
        val list = mutableListOf<Pair<Int,Int>>()

        var left = (-1e9).toInt()
        var right = (-1e9).toInt()
        var result = 0

        repeat(n){
            val (x,y) = readLine()!!.split(' ').map { it.toInt() }
            list.add(Pair(x,y))
        }

        list.sortBy { it.first }

        for(i in 0 until n){
            // 만약 , x좌표가 기존의 right보다 작다면 , 이는 합칠 수 있는 선분임
            if(list[i].first < right){
                right = max(right,list[i].second) // 합침
            } else { // 합칠 수 없는 선분이라면 , 혹은 반복문의 첫번째 단계라면
                result += (right - left) // 그 전까지의 선분들을 전부 계산하고
                left = list[i].first // 새로운 왼쪽과
                right = list[i].second // 새로운 오른쪽으로 갱신후 다시 작업을 진행한다
            }
        }

        result += right - left
        println(result)
    }
}

깨달은 점

그리디 알고리즘을 하다보면 정렬한 후에 작업을 해야하는 경우가 있는데 정렬에 대해서 좀 더 공부가 필요하다고 생각했다.

시간복잡도에 보다 신경을 써야할 거 같다.

이와 관련된 문제는 쉽지 않다...😂