라인 스위핑 (Line Sweeping)

라인 스위핑 ( Line Sweeping ) 알고리즘

• 선 하나를 여러 가지 상황에서 움직이면서 문제를 해결하는 방법
• 공간이나 직선 상에서 한쪽 시작 점을 기준으로, 반대편 종료 지점 까지 Scan 하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단 기준이 되는 기준을 적용해주면 정답이 구해지는 형태
• 일반적으로 평면 상의 선이나 구간과 관련된 문제를 해결하는데 사용
• 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것
• 좌표 문제에 많이 사용되며, O(NlogN)의 시간 복잡도를 가진다.

💡스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현해야 한다.

문제 예시 - BOJ2109

문제

한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

입력

첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 각 대학에서 제시한 p값과 d값이 주어진다.

출력

첫째 줄에 최대로 벌 수 있는 돈을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class lecture implements Comparable<lecture> {
        int day, money;

        public lecture(int day, int money) {
            this.day = day;
            this.money = money;
        }

        @Override
        public int compareTo(lecture o) {
            return this.day - o.day;
        }
    }
    private static int N;
    private static List<lecture> lectures = new ArrayList<>();
    private static PriorityQueue<Integer> pq = new PriorityQueue<>();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int answer;
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        answer = 0;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int money = Integer.parseInt(st.nextToken());
            int day = Integer.parseInt(st.nextToken());
            lectures.add(new lecture(day, money));
        }
        
        Collections.sort(lectures);
        
        for (int i = 0; i < N; i++) {
            pq.add(lectures.get(i).money); // 돈을 넣어준다
            if(pq.size() > lectures.get(i).day) pq.poll();
        }

        while (!pq.isEmpty()) {
            answer += pq.poll();;
        }

        System.out.println(answer);
    }
}

느낀점

라인 스위핑이라는 것을 처음 접해봐서, 해당 문제가 라인 스위핑으로 어떻게 해결할 수 있을지에 관해 많이 고민했다. 라인 스위핑을 구현하는데에는 2가지 방법이 있다는 이야기를 듣고 답안을 본 이후 구현했다. 다음엔 라인 스위핑 정석 문제를 풀이해보고 싶다.