[BOJ/python]2836번 수상 택시

백준 2836번 수상 택시 파이썬

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

2836번: 수상 택시

스위핑 알고리즘 문제이다. 스위핑 알고리즘이라고 해서 특별한 방법이 있는 것은 아닌 것 같고 전체를 탐색하며 마주하는 이벤트를 바로바로 처리하면서 푸는 유형이다. 그렇기 때문에 스위핑 자체에 집중하기보다 시간복잡도를 줄여 문제를 풀기 위한 방법을 떠올려야 한다.

---

M명의 사람을 모두 태울 수 있기 때문에 순방향 구간을 태워줘야 하는 경우 신경 쓸 필요가 없다. 0번 집부터 M번 집까지 출발지가 있다면 친구를 태우고 목적지가 있다면 내려주면 된다.

---

역방향 구간에서는 가장 먼저 등장하는 구간의 친구를 먼저 태워줘야 한다. 위와 같이 태워줘야 하는 친구가 3명이 있다고 생각해보자. (출발지와 목적지 사이 거리 각각 a, b, c, 모두 역방향)

start에서 출발해서 end까지 가기 위해

• 모든 친구를 한 번에 태워서 한 번에 내려주는 경우 : 3(a+b+c+x+y)
  • a + x + b + y + c (모든 친구 탑승)
  • a + x + b + y + c (모든 친구 하차)
  • a + x + b + y + c (start에서 end로)
• 먼저 만나는 친구를 먼저 내려주는 경우 : 3(a+b+c) + x + y
  • a + a (a 탑승, a 하차)
  • a + x (b 목적지 앞 까지 이동)
  • b + b (b 탑승, b 하차)
  • b + y (c 목적지 앞까지 이동)
  • c + c(c탑승, c 하차)

---

이번에는, 위와 같이 역방향 구간에서 겹치는 경우가 발생한다고 하자.

start에서 출발해서 end까지 가기 위해

• 2명의 친구를 한 번에 태워서 한 번에 내려주는 경우 : 3(a+b-k)
  • a + b - k (모든 친구 탑승)
  • a + b - k (모든 친구 하차)
  • a + b - k (start에서 end로)
• 먼저 만나는 친구를 먼저 내려주는 경우 : 3(a+b) - k
  • a + a (a 탑승, a 하차)
  • a + b - k (b 탑승)
  • b (b 하차)
  • b (b 목적지에서 end로 이동)

역방향 구간이 겹치면 모든 친구를 한 번에 태워서 한 번에 내려주면 된다. 즉, 역방향 구간이 겹친다면 하나의 구간으로 만들어 준다.

---

모든 역방향 구간을 정리하면 다시 위와 같은 형태가 될 것이다. start에서 end 까지 가는 경우의 최소 거리는 3(a+b+c) + x + y 이었다. 전체 구간의 길이가 a+b+c+x+y 이므로 역방향 구간을 한 번씩 반복하고 이동한 경우 최소 거리이다.

결국 이동해야 하는 거리의 최솟값은 전체 길이 + (구간의 길이의 합)*2 이다.

1. 풀이

• 역방향으로 태워줘야하는 경우의 출발지와 목적지를 L 배열에 저장한다. (출발지의 번호가 더 크다. 생각하기 편하게 [목적지, 출발지] 형태로 저장한다.)
• 출발지의 번호를 내림차순으로 정렬한다.
• L 배열을 탐색하며
  • 이전 구간에 포함되면 구간의 범위를 갱신한다.
  • 이전 구간에 포함되지 않으면 이전 구간은 tmp 배열에 추가하고 새로운 구간을 만든다.
• tmp 배열에 있는 모든 구간마다 (구간의 길이 * 2)를 answer에 추가한다.

2. 코드

L = []
N, M = map(int, input().split())
for _ in range(N):
    s, e  =map(int, input().split())
    if s>e : 
        L.append([e,s])

L.sort(key = lambda x: -x[1])
tmp = []
ts, te = L[0]
for i in range(1,len(L)):
    s,e = L[i]
    
    if ts <= e : # <=te (sort에 의해 보장됨)
        ts = min(ts,s)
    
    else:   #e < ts 
        tmp.append([ts,te])
        ts, te = s,e

tmp.append([ts,te])

answer = M
for i in range(len(tmp)):
    answer += 2*(tmp[i][1] - tmp[i][0])
    
print(answer)