[BOJ 2170] 선 긋기

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

문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

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

입력

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

출력

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

제한

시간 제한	메모리 제한
1sec	192MB

---

풀이

우리가 구해야하는 문제가 정확히 무엇인지 생각해보자. 각 선들의 정보가 주어졌을 때 그려진 선의 총 길이를 계산하는 것이 문제다. 이 때, 겹친 선은 중복해서 세지 않는다는 것이 조건이다.

각 선은 시작점과 도착점이 있다. 이걸 구조체로 묶어서 하나의 선의 정보를 기록하도록 하자. 대충 아래와 같을 것이다.

typedef struct Line {
    int x, y;
} Line;

그리고 “두 선의 범위가 겹친다면” 두 선을 합쳐 하나의 선으로 표현할 수 있다. 이 방식으로 겹치는 선들을 모두 합쳐서 하나의 선으로 바꿀 수 있으면, 남아있는 선들의 길이 총합을 구하면 정답을 얻어낼 수 있을 것이다.

그럼 범위가 겹치는 선들을 어떻게 구할 수 있을까? 내가 사용한 방법은 “시작점에 대한 오름차순 정렬”이다. 이러면 $1 \leq i < j \leq N$인 두 index $i$, $j$에 대해 $x[i] \leq x[j]$가 항상 보장된다. 그러므로 두 범위가 겹치는지의 여부는 $x[j] \leq y[i]$만 확인하면 된다. 겹친다면 끝점을 $\max(y[i], y[j])$로 업데이트할 수 있다 (시작점은 $x[i]$로 고정). 만약 겹치지 않는다면 그 선은 다른 선들과 분리된 선이므로 결과값에 그 길이를 더해줄 수 있다. 그 길이는 $y[i] - x[i]$가 될 것이다!

즉, 각 선들의 정보를 입력받고 정렬해둔 다음, 겹침 여부를 판단하며 각 선들을 최대한 합쳐둔다. 최종 결과에 길이의 합을 출력하는 것으로 문제를 해결할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 :