국경을 따라 순환 도로를 건설한 국가가 있다. 이 순환 도로에는 N개의 위치에 버스 정류소가 있으며, 버스 정류소에는 0부터 N-1까지 번호가 시계방향 순서로 지정되어 있다. 현재 여러 개의 버스 노선들이 이 순환 도로에서 운행되고 있다. 각 버스 노선은 [a, b]로 표시된다. 이 노선의 버스는 버스 정류소 a부터 b까지를 시계방향으로, b부터 a까지는 반시계방향으로 운행한다. 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.
국가 교통행정부에서 비용 절감을 위해서 버스 노선 중 일부를 취소하려고 한다. 취소되는 노선은 다른 노선에 포함되어 있는 노선이다. 예를 들어, N=10일 때, 5개의 버스 노선이 다음과 같이 있다고 하자.
위 그림에서 버스 노선 ①은 ⑤에 포함되고, 버스 노선 ④는 ③에 포함된다. 버스 노선 ②, ③, ⑤를 포함하는 노선은 없다. 따라서 취소되는 버스 노선은 ①과 ④이다.
버스 노선에 대한 정보가 주어질 때, 취소되지 않고 계속 운행되는 버스 노선을 모두 출력하는 프로그램을 작성하시오.
첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개의 줄에는 1번 노선부터 순서대로 각 버스 노선 [a, b]를 나타내는 두 개의 정수 a와 b가 한 줄에 주어진다, 단, 0 ≤ a, b ≤ N-1이고 a ≠ b이며 동일한 버스 노선이 두 번 이상 입력으로 주어지는 경우는 없다. 또한 순환 도로 상의 모든 정류소를 포함하는 버스 노선은 존재하지 않는다.
출력
입력으로 주어진 버스 노선들 중에서 다른 노선에 포함되지 않은 노선들의 번호를 번호가 작은 것부터 순서대로 빈칸을 사이에 두고 출력한다.
입력 예시
10
5
0 4
2 6
5 0
7 9
9 4
출력 예시
2 3 5
풀이
이런 문제에 익숙치 않아서 그런가, 엄청 헤맸다. 분명히 라인스위핑 문제는 이전에 풀어보았음에도 불구하고 제대로 기억해내지 못했었다.
라인스위핑 알고리즘은 그리디 알고리즘의 원칙을 따른다. 우선 평면을 전제로 하고, 각 라인을 (시작점, 끝점)으로 표현할 때 라인 리스트를 시작점을 기준으로 오름차순, 같은 시작점일 경우 끝점을 기준으로 내림차순으로 정렬하자.
이 경우, 라인 리스트의 각 원소는 바로 뒤의 원소들의 시작점과 비교하였을 때 작거나 같은 시작점을 가지게 된다.
이제 끝점에 대해 생각해 보자. 직전에 저장된 라인을 기준으로 다음 라인이 겹치는지 여부는 끝점만을 판단하면 된다. 앞서 말했듯, 다음 라인의 시작점은 무조건 직전의 라인보다 크거나 같으므로 직전 라인에 포함되거나 벗어나게 된다. 즉 지금의 라인의 끝점이 직전에 저장된 라인의 끝점보다 작다면, 이 라인은 직전에 저장된 라인에 포함되므로 배제하게 된다. 그렇지 않다면, 부분적으로 겹치거나 겹치는 부분이 없다는 의미이므로 그 라인을 저장한다.
또한 이 라인은 순환 구조이므로, 다음과 같은 두 가지 경우를 생각해보아야 한다.
순환점인 0을 포함하지 않을 경우(a) : 시작점 < 끝점을 만족한다. 이들을 따로 리스트로 저장한다면 위의 라인 스위핑 알고리즘으로 모든 경우를 판단 가능하다.
순환점인 0을 포함할 경우(b) : 시작점 > 끝점을 만족한다. 이 경우 역시 끝점에 전체 크기 N을 더해 주면 시작점 < 끝점을 만족하므로 따로 저장하여 라인 스위핑 알고리즘으로 모든 경우를 판단한다.
이렇게 두 가지 경우로 나누었을 때, 결과적으로 두 개의 라인 리스트 a, b가 발생하게 된다. 이제 세 번째 경우를 생각해 보자.
a의 원소가 b의 원소를 포함하는 경우는 전혀 없음이 자명하다.
b의 원소가 a의 원소를 포함하는 경우를 생각해 보자.
다음과 같은 경우에 a의 원소는 b의 원소에 포함되게 된다.
b를 정렬하였을 때, 첫 번째 원소의 시작점이 a의 원소의 시작점보다 작은 경우
마지막 원소의 끝점이 a의 원소의 끝점보다 큰 경우.
즉 이 경우들을 제거하고, 남은 a원소 리스트와 b원소 리스트를 합쳐 정렬한 값이 정답이 된다.
풀이 코드
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
def init() :
route_list_a = list()
route_list_b = list()
for i in range(M) :
start, end = map(int, input().split())
if start > end :
route_list_b.append((i+1, start, end+N))
else :
route_list_a.append((i+1, start, end))
return route_list_a, route_list_b
def traversal(lst, mode = 1) :
lst.sort(key = lambda x : (x[1], -x[2]))
result = list()
for idx, start, end in lst :
if result and result[-1][2] >= end :
continue
result.append((idx, start, end))
return result
def extract(lst1, lst2) :
result = list()
if lst2 :
result.extend([x[0] for x in lst2])
_, min_start, _ = lst2[0]
_, _, max_end = lst2[-1]
lst1 = [ x for x in lst1 if not ( x[1] >= min_start or x[2] <= max_end-N ) ]
result.extend([x[0] for x in lst1])
result.sort()
return result
def solve() :
route_list_a, route_list_b = init()
result1 = traversal(route_list_a, 1)
result2 = traversal(route_list_b, 2)
result = extract(result1, result2)
print(*result)
solve()
