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

Line Sweeping

Sweeping이라는 단어를 번역하면 "싹슬이 하는"이라는 뜻을 가집니다.

즉, "한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것"입니다.

보통  라인스위핑 알고리즘은 좌표 문제에 많이 사용되며 O(nlogN)의 시간 복잡도를 가집니다.

 

 

라인 스위핑 알고리즘 문제 (백준 2170 : 선 긋기)

문제 설명

매우 큰 도화지에 자를 대고 선을 그으려고 한다.

매우 큰 도화지에 자를 대고 선을 그으려고 한다.

선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다.

선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

 

입력

첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

 

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

n	lines	result
4	[[1, 3], [2, 5], [3, 5], [6, 7]	5

 

---

풀이

위의 입력값 대로 그림을 그려보면 다음과 같습니다.

result = 5가 어떻게 나오는지 봅시다.

파란색 선(1, 3)과 초록색 선(2, 5)를 비교했을 때 두 선이 겹치기 때문에 두 선을 합칠 수 있습니다. => 합친 선 (1, 5)

합친 선(1, 5)과 빨간 색(3, 5)를 비교합니다. 이 빨간색 선이 합친 선에 포함되기 때문에 변함이 없습니다.

합친 선(1, 5)와 보라색 선(6, 7)을 비교합니다. 이 두선은 서로 겹치거나 이어져 있지 않기 때문에 절대 합칠 수 가 없습니다.

그렇기 때문에 보라색 선의 길이를 따로 더해줘야합니다.

n = 4로 4개의 선을 다 탐색한 결과 합친 선(1, 5)와 보라색 선(6, 7) 남았습니다.

합친 선의 길이는 5 -1 = 4, 보라색 선의 길이는 7 - 6 = 1으로 두 선의 길이를 합치면 그은 선의 총 길이 = 5가 됩니다.

 

선 긋기 코드

package algorithm;

import java.util.Arrays;

public class LineSweeping {
    public static void main(String[] args) {
        int n = 4;
        int[][] lines = new int[][]{{1, 3}, {2, 5}, {3, 5}, {6, 7}};
        System.out.println(getLineLength(n, lines));
    }

    public static int getLineLength(int n, int[][] lines) {
        // x좌표가 서로 같으면 y좌표 오름차순 정렬, 서로 다르면 x좌표 오름차순 정렬.
        Arrays.sort(lines, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            } else {
                return o1[0] - o2[0];
            }
        });

        int prevX = lines[0][0]; // 이전 선의 x좌표
        int prevY = lines[0][1]; // 이전 선의 y좌표
        int len = prevY - prevX; // 현재 선의 길이

        for (int i = 1; i < n; i++) {
            int currentX = lines[i][0]; // 현재 선의 x좌표
            int currentY = lines[i][1]; // 현재 선의 y좌표

            /*
            현재 선의 x가 이전 선의 x보다 크거나 같고,현재 선의 y가 이전 선의 y보다 크거나 작다면
            현재 선이 이전 선에 포함되므로 다음 선으로 넘어간다.
             */
            if (prevX <= currentX && currentY <= prevY) {
                continue;
            }
            // 현재 선이 이전 선에 포함된다면, 두 선을 이어 붙인다.
            if (currentX < prevY) {
                len += currentY - prevY;
            }
            // 현재 선이 이전 선과 겹치지 않는다면, 겹치지 않는 선의 길이를 더한다.
            if (currentX > prevY){
                len += currentY - currentX;
            }
            // 이전 선을 현재 선으로 변경한다.
            prevX = currentX;
            prevY = currentY;
        }

        return len;
    }
}