[개념정리] 스위핑 알고리즘

스위핑 알고리즘이란 특정 기준에 따라 정렬된 순서대로 문제를 처리하는 방법이다. 스위핑 알고리즘을 사용해야하는 문제들의 특징은 러프한 방법 (일반적으로 O(N^2)의 시간복잡도를 갖는 방법)으로는 해결이 불가능하며, DP를 사용하기에는 메모이제이션 해야할 수가 너무 많은 경우가 일반적이다. 스위핑 알고리즘으로 문제를 풀 경우, 해당 시간 복잡도는 정렬에서 발생하는 O(NlogN)안에서 해결된다.

---

백준 - 8982. 사냥꾼

일반적인 방법으로 풀게되면 O(N*M)의 시간복잡도를 가지게 되고 시간초과가 발생한다. 그렇다고 좌표에 대한 정보를 기억할 수도 없기 때문에 스위핑 알고리즘을 통해 해결해야 한다. 

먼저, 사대와 동물을 모두 x축 순서로 정렬하고 동물을 기준으로 사냥이 가능한지 확인한다. 확인 과정은 동물의 x좌표보다 작은 사대를 찾고 해당 사대와 바로 다음 사대에서 거리가 L 이하면 사냥이 가능한 것으로 판별한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {
	static class Pair implements Comparable<Pair>{
		int x;
		int y;
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override
		public int compareTo(Pair o) {
			if (this.x > o.x) {
				return 1;
			} else if (this.x == o.x && this.y > o.x) {
				return 1;
			}
			return -1;
		}
	}
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int M, N, L, startIdx = 0, cnt;
	static int[] shoot;
	static Pair[] animal;
	public static void main(String[] args) throws IOException {
		String[] input = br.readLine().split(" ");
		M = Integer.parseInt(input[0]);
		N = Integer.parseInt(input[1]);
		L = Integer.parseInt(input[2]);
		
		shoot = new int[M];
		animal = new Pair[N];
		String[] shootLine = br.readLine().split(" ");
		for (int i = 0; i < M; i++) {
			shoot[i] = Integer.parseInt(shootLine[i]);
		}
		
		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			animal[i] = new Pair(Integer.parseInt(line[0]), Integer.parseInt(line[1]));
		}
		
		Arrays.sort(shoot);
		Arrays.sort(animal);

		for (int i = 0; i < N; i++) {
			shoot(i);
		}

		System.out.println(cnt);
	}
	
	static void shoot(int idx) {
		int shootIdx = 0;
		while(shootIdx != M-1 && shoot[shootIdx] <= animal[idx].x) {
			shootIdx++;
		}
		
		if (--shootIdx >= 0 && Math.abs(shoot[shootIdx] - animal[idx].x) + animal[idx].y <= L) {
			cnt +=1;
		} else if(++shootIdx < M && Math.abs(shoot[shootIdx] - animal[idx].x) + animal[idx].y <= L) {
			cnt+= 1;
		}
		return;
	}
}

 

---

백준 - 2170. 선긋기

이 문제도 역시 일반적인 방법을 통해 해결하려고 하면 시간 초과가 발생하고, 좌표에 대한 선 여부를 저장하기에는 두 점의 위치 범위가 너무 크다. 따라서 스위핑 알고리즘을 사용해서 해결하였다.

먼저 x를 기준으로 x가 같다면 y를 기준으로 정렬한다. 이후 현재 end가 다음 쌍의 start보다 큰 경우에는 겹치는 구간이 존재하기 때문에 end 값을 큰 값으로 갱신한다. 현재 end가 다음 쌍의 start보다 작은 경우에는 겹치지 않는 새로운 선분의 시작으로 보고 이전 선분의 길이 (end - start)를 더해주고 start, end를 갱신해준다.

풀이

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

public class Solution1 {
	static class Pair implements Comparable<Pair>{
		int start;
		int end;
		public Pair(int start, int end) {
			this.start = start;
			this.end = end;
		}
		@Override
		public int compareTo(Pair o) {
			if (this.start > o.start) {
				return 1;
			} else if (this.start == o.start && this.end > o.end) {
				return 1;
			}
			return -1;
		}
		
	}
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int N;
	static Pair[] points;
	public static void main(String[] args) throws NumberFormatException, IOException {
		N = Integer.parseInt(br.readLine());
		points = new Pair[N];
		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			points[i] = new Pair(Integer.parseInt(line[0]), Integer.parseInt(line[1]));
		}
		
		Arrays.sort(points);
		
		int curIdx = 0;
		int distance = 0;
		while(curIdx < N) {
			int start = points[curIdx].start;
			int end = points[curIdx].end;
			while(++curIdx < N) {
				if (points[curIdx].start <= end) 
					end = Math.max(end, points[curIdx].end);
				else 
					break;
			}
			distance += (end - start);
		}
		
		System.out.println(distance);
	}
}