[백준] 철도 (스위핑(Line Sweep))

문제 소개

백준 13334번 철도 문제를 스위핑(Line Sweep) 알고리즘으로 정리합니다.

이 문제는 길이가 d로 고정된 철로 선분에서 집과 사무실이 모두 포함되는 사람 수의 최댓값을 구하는 문제입니다.

핵심은 이벤트 기반 스위핑으로 구간을 효율적으로 처리하여 최적해를 찾는 데 있습니다.

문제 링크: 철도 - 백준 13334번

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 문제 조건 분석: 길이 d인 철로 선분에 집과 사무실이 모두 포함되어야 함
2. 불가능한 경우 제거: 집과 사무실 거리가 d보다 큰 사람들은 애초에 불가능
3. 구간 문제로 변환: 각 사람마다 "이 사람을 포함할 수 있는 철로 구간"을 계산
4. 이벤트 스위핑: 철로의 오른쪽 끝점을 기준으로 스위핑하며 최대 겹치는 구간 수 계산
   1. 모든 가능한 철로 위치를 확인하면 O(좌표 범위)로 시간초과
   2. 투 포인터도 가능하지만 좀 더 시간 걸림 (둘 다 정렬로 시간 복잡도는 O(nlogn))

위 : 스위핑, 아래 슬라이딩 윈도

 

---

해결 과정 및 코드

핵심 아이디어

1. 좌표 정규화: 집과 사무실 위치를 (작은 값, 큰 값) 순서로 정렬 (임의로 작은 값 = home, 큰 값 = office 로 지정)
2. 유효 구간 계산: 각 사람을 포함할 수 있는 철로의 범위는 [office-d, office]
3. 이벤트 생성: 철로 끝점이 office일 때 +1, home+d+1일 때 -1 이벤트 생성
   • 철로 끝점이 home+d+1 이 되면 home 이 제외
4. 스위핑: 이벤트를 철로 끝점 순으로 정렬하여 처리하며 최댓값 갱신

코드

시간 복잡도: O(N log N)
공간 복잡도: O(N)

import java.io.*;
import java.util.*;

public class Main {
	static class Event {
		final int railEnd, change;  // 철로 끝점과 변화량
		
		Event(int railEnd, int change) {
			this.railEnd = railEnd;
			this.change = change;
		}
	}
	
	public static void main(String[] args) throws IOException {
		int N = read();
		int[][] data = new int[N][2];
		
		// 각 사람의 집과 사무실 입력 (작은 값이 앞에 오도록 정렬)
		for (int i = 0; i < N; i++) {
			int home = read(), office = read();
			if (home > office) {
				int temp = home;
				home = office;
				office = temp;
			}
			data[i] = new int[] { home, office };
		}
		
		int d = read();
		
		// 이벤트 우선순위 큐 (철로 끝점 기준 정렬)
		PriorityQueue<Event> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.railEnd));
		
		for (int i = 0; i < N; i++) {
			// 집과 사무실 거리가 d보다 크면 불가능하므로 제외
			if (data[i][1] - data[i][0] > d) continue;
			
			// 이 사람을 포함할 수 있는 철로 구간: [office-d, office]
			pq.offer(new Event(data[i][1], 1));        // 철로가 office에 도달하면 +1
			pq.offer(new Event(data[i][0] + d + 1, -1)); // 철로가 home+d를 넘으면 -1
		}
		
		int max = 0, cnt = 0;
		
		// 스위핑: 철로 끝점 순서로 이벤트 처리
		while (!pq.isEmpty()) {
			Event e = pq.poll();
			cnt += e.change;
			
			// 같은 철로 끝점에서 발생하는 모든 이벤트 처리
			while (!pq.isEmpty() && pq.peek().railEnd == e.railEnd) {
				cnt += pq.poll().change;
			}
			
			max = Math.max(max, cnt); // 현재까지 최댓값 갱신
		}
		
		System.out.println(max);
	}

	// 빠른 입력을 위한 read 함수
	public static int read() throws IOException {
		int cur, n = System.in.read() & 15;
		boolean isNegative = (n == 13);
		if (isNegative) n = System.in.read() & 15;
		while ((cur = System.in.read()) > 32) n = (n << 3) + (n << 1) + (cur & 15);
		return isNegative ? -n : n;
	}
}

---

참고 - 스위핑 알고리즘이란?

스위핑(Line Sweep) 알고리즘이란?
한 방향으로 선을 이동시키며 이벤트가 발생하는 지점에서 상태를 갱신하는 알고리즘입니다.

이 문제에서의 적용:

• 스위핑 기준: 철로의 오른쪽 끝점
• 이벤트 정의: 사람이 포함되기 시작하는 지점(+1), 포함이 끝나는 지점(-1)
• 상태 관리: 현재 철로에 포함된 사람의 수

스위핑의 장점:

• 시간 효율: 모든 가능한 구간을 직접 확인하지 않고도 최적해 계산
• 공간 효율: 이벤트 기반으로 필요한 정보만 저장
• 구현 간결: 복잡한 구간 겹침 문제를 단순한 이벤트 처리로 해결

스위핑 라인 알고리즘 ( Sweep line algorithm )