[BOJ - 23740 | Python 3] 버스 노선 개편하기

https://www.acmicpc.net/problem/23740

#스위핑

 

문제의 기본 개념을 모르고 무식하게 박치기를 한 흔적...

 

문제 요약

시작점과 끝점(s, e)으로 구성된 n개의 버스 노선 중 겹치는 구간이 있는 노선을 병합하여 중복 노선을 최소화하는 문제

버스 노선을 합칠 때, 요금은 더 낮은 값을 따른다.

---

 

우선 스위핑이 무엇인지 알아볼 필요가 있습니다.

 

Sweeping

라인 스위핑이라고도 불리며, "쓸어 모으다" 라는 뜻이 있습니다. (일반적으로) 한 방향으로 탐색해가며 특정 연산을 진행하는 것입니다. 스위핑은 스택이나 정확한 솔루션이 존재하는 알고리즘처럼 정해진 방법은 없으며 하나의 개념이라고 생각하시면 됩니다. 우리는 한 방향으로 탐색할 것이기 때문에, 탐색할 방향으로 정렬된 상태여야 합니다. 우리가 풀어야 할 문제인 버스 노선으로 살펴봅시다.

 

버스 노선들. 5번 노선을 제외하면 백준의 1번 예제와 모두 같습니다.

 

이 좌표평면은 특정 경우를 시각화한 것입니다. (y값은 무관합니다.) 1번, 4번, 5번 노선이 서로 겹치는 부분이 보이시나요? 이 노선들은 문제의 병합할 노선에 해당하는 중복 노선입니다. 마찬가지로 2번, 3번, 6번도 겹치는 노선이므로 하나의 노선으로 합쳐집니다. 그렇게 최종적으로 두 노선이 남게 됩니다.

 

 

합쳐진 A 노선 중 가장 저렴한 1번 노선의 값인 4원을 계승하고, B 노선은 2번 노선인 5원을 계승합니다. 처음으로 알아본 예시의 정답이 나왔습니다.

 

 

문제에도 나와 있지만, 예시에서도 볼 수 있듯 한 점 이상에서 겹친다면 중복된 노선으로 취급한다는 것이 중요합니다. 따라서 위 노선은 아래처럼 됩니다.

 

 

한 점 이상에서 겹쳐지는 노선은 전부 합쳐지므로 시작점 s가 빠른 순서로 정렬한 후 어떤 버스 노선과 비교하려는 다른 버스 노선이 겹쳐지는 것을 확인했다면 합치고 더 낮은 요금을 갱신한 뒤, 다음 비교 대상으로 넘어가며 모든 노선을 비교합니다. 겹침의 판별은 기준이 된 버스 노선 A[s, e]와 비교할 버스 노선 B[s, e]가 있다고 할 때, A[e] >= B[s]라면 버스 노선 B는 A와 겹친다는 것을 의미합니다. 다양한 경우를 직접 그려보면 이해가 더 빠를 것입니다.

 

만약 s가 빠른 순서로 정렬을 하지 않았다면  A[e] >= B[s]를 만족하지만 A[s] < B[e]인 경우가 생겨나게 되어 단순하게 한 번의 비교만으로는 판단하기 어려울 것입니다.

 

A[s]  <  B[e] 인  경우. 실제로는 겹쳐지지 않은 노선

 

우리는 노선들을 s가 작은 순서로 정렬하고, 정렬된 노선들 중 첫번째 노선이 기준이 되며 다른 모든 노선에 겹침 비교 연산을 하며 쭉 탐색하는 코드를 구현하게 되겠죠. 이를 스위핑이라 합니다.

 

Python 3

import sys

n = int(sys.stdin.readline())
line = list()
result = list()

for _ in range(n):
    s, e, c = map(int,sys.stdin.readline().split())
    line.append((s, e, c))
    
line.sort()
targetA = line[0]

for i in range(1, n):
    targetB = line[i]
    
    #print("A:", targetA[1])
    #print("B:", targetB)
    
    if targetA[1] >= targetB[0]:
        targetA = (targetA[0], max(targetA[1], targetB[1]), min(targetA[2], targetB[2]))
    else:
        result.append(targetA)
        targetA = line[i]

if targetA not in result:
    result.append(targetA)

print(len(result))
for i in range(len(result)):
    print(*result[i])

 

이제보니 테스트용 주석을 안빼고 제출했네요? 불-편 :thinking: