[백준][C++] 2170: 선 긋기

문제 링크: https://www.acmicpc.net/problem/2170

 

스위핑 문제입니다.

문제를 보자마자 생각할 수 있는 풀이는 점의 범위만큼 배열을 만든 다음, 선을 직접 다 그은 다음 배열을 한번 순회하면서 선이 그어진 칸을 세는 방법이 있겠습니다. 하지만 점의 범위가 [-10억, 10억]이기 때문에 불가능합니다.

이 때 사용할 수 있는 방법이 스위핑(sweeping)으로, 전체 공간을 한번만 잘 스캔하면서 마주치는 요소들을 적당히 처리해주면 답을 구할 수 있습니다.

 

선을 (시작, 끝)으로 나타낸 다음 시작점 기준 오름차순으로 정렬합니다. 선 목록을 한번 순회(sweeping)하면서 아래 과정을 거칩니다

• 앞의 선과 겹치는지 확인
  • 겹치면 하나의 선분으로 연장한다
  • 겹치지 않으면 앞까지의 선분 길이만큼을 sum 변수에 더한다
• sweeping이 끝나면 마지막 선분 길이만큼 sum 변수에 더한다

 

겹치는 것은 (다음 선분의 시작 <= 이전 선분의 끝) 여부를 확인하면 되겠습니다

 

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
#include <bits/stdc++.h>
using namespace std;


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	
	vector<pair<int, int>> vp(n);
	for (auto& [from, to] : vp)
		cin >> from >> to;

	sort(vp.begin(), vp.end());

	int sum = 0;
	int start = vp[0].first, end = vp[0].second;
	for (int i = 1; i < n; ++i) {
		if (vp[i].first <= end)
			end = max(end, vp[i].second);
		else {
			sum += end - start;
			start = vp[i].first;
			end = vp[i].second;
		}
	}
	sum += end - start;
	cout << sum << '\n';

	return 0;
}