[BOJ] 2170 - 선 긋기

이준기·2022년 2월 8일

문제 링크

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)가 주어진다.

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

문제 풀이

입력 데이터 크기가 20억이나 된다! 배열을 이용하거나 완전 탐색으로 하나하나 보는 것은 무리일것으로... 다른 아이디어가 필요했다.

사실은 라인스위핑이라는 알고리즘을 공부하다가 찾은 문제인데, 라인스위핑이 무슨 알고리즘 일까?

스위핑 알고리즘

어떤 선이나 공간을 한쪽에서부터 싹 쓸어버리는 것이라고 한다.

즉, 무언가 기준으로 한 번만 전체 공간을 스캔하며 마주치는 요소들에 대해 뭔가를 해주면 정답이 구해진다. (=가지치기)

한 쪽에서 부터 쓸어오므로 완전 탐색보다 빠르고 기준에 따라 시간복잡도가 결정되는 것 같다.

문제 적용

겹치는 부분들을 전부 합치고, 합쳐진 최종 선들의 길이만 더해주면 정답이 된다. 순서는 아래와 같다.

우선 시작점을 기준으로 주어진 선분들을 정렬한다. -> 스캔의 기준이 된다.
정렬된 선분들을 비교하여 합칠 수 있으면 합치고, 아니면 선분을 추가한다. -> 한 쪽부터 쓸어가게 되므로 순서의 제약을 받지 않고 다 스캔하게 됨
완성된 선분들의 길이를 더해주면 정답이 됨

맞은 코드

n = int(input())
linear = []
ans = []

for _ in range(n):
  s, e = map(int, input().split())
  linear.append((s,e))

linear.sort(key=lambda x:x[0])
nowStart, nowEnd = linear[0]

for start, end in linear:
  if start <= nowEnd:
    if end >= nowEnd:
      nowEnd = end
  elif start > nowEnd:
    ans.append((nowStart, nowEnd))
    nowStart = start
    nowEnd = end

ans.append((nowStart, nowEnd))

sum = 0
for start, end in ans:
  sum += end - start

# print(ans)
print(sum)