백준 21342 - Flight Collision (Python)

문제 정보

• https://www.acmicpc.net/problem/21342
• 연결 리스트, 우선순위 큐

---

문제 정리

수직선 위에 $N \leq 100,000$개의 드론이 일정한 속도로 움직이고 있다.
두 드론이 같은 위치에 도달하는 순간 충돌하며 사라지게 된다.
드론의 초기 위치와 속도를 알 때, 영원히 충돌하지 않고 계속 비행할 수 있는 드론을 알아내야 한다.

---

풀이

• 먼저, 한 가지 관찰을 해야 한다.
  충돌은 반드시 서로 이웃한 두 드론 쌍 사이에서만 발생한다.

• 또한, 이웃한 드론 i와 드론 j가 서로 충돌하기 위한 조건은 $v_i > v_j$이다. 즉, 왼쪽 드론의 속도가 오른쪽 드론의 속도보다 더 빨라야 한다는 것이다.
  이 때의 충돌 시간은 $t = \frac{x_j-x_i}{v_i-v_j}$ 가 된다.

• 초기 상태에서 충돌이 일어날 수 있는 쌍은 (1번 드론, 2번 드론), (2번 드론, 3번 드론), ..., (N-1번 드론, N번 드론) 이다.
  따라서, 두 드론이 충돌하는 시간과 충돌하는 드론의 번호를 저장해준다.

• 드론이 충돌하면 두 드론 모두 사라지므로, 충돌한 두 드론의 왼쪽, 오른쪽에 있는 살아있는 드론이 새로운 이웃 쌍이 된다.

• 매번 충돌이 일어날 때마다 새로운 이웃 쌍을 찾기 위해 이웃 드론을 하나씩 체크하며 살아있는지 확인할 경우 TLE가 발생하게 된다. (최대 충돌 횟수는 $N/2$회이기 때문에)
  따라서, 이웃한 드론의 번호를 O(1)에 구해주는 연결 리스트를 만들어 해결할 수 있다.

• 시간 순서대로 충돌하는 드론을 삭제해가야 하므로, 아까 만들어뒀던 충돌 시간이 저장된 충돌 쌍을 우선순위 큐로 만들어 처리하면 된다.

• 주의해야 할 점은 실수 오차이다. 충돌 시간은 분수 형태이므로, 수가 커지게 되면 실수 오차가 발생할 수 있다.
  따라서 충돌 시간 자체를 저장하지 말고 충돌 시간의 분자, 분모를 따로 저장한 뒤 __lt__ 함수를 따로 만들어 비교할 때 $x_iv_j < v_jx_i$처럼 교차곱을 이용해 비교해 주면 된다.

---

후기

실수 오차...

---

코드

# 백준 21342

import io
import heapq

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


class Event:
    def __init__(self, dx, dv, left, right):
        self.dx = dx
        self.dv = dv
        self.left = left
        self.right = right
    
    def __lt__(self, other):
        a = self.dx * other.dv
        b = other.dx * self.dv
        if a != b:
            return a < b


def solve(N, drone):
    # 살아있는 드론 간 연결 리스트를 [생존 여부, 왼쪽 드론 번호, 오른쪽 드론 번호]로 생성
    isAlive = [[1, None, None]]
    for i in range(1, N):
        isAlive[i-1][2] = i
        isAlive.append([1, i-1, None])

    # 충돌 사건을 [충돌 시간(분자), 충돌 시간(분모), 왼쪽 충돌 드론 번호, 오른쪽 충돌 드론 번호]로 저장
    pq = []
    for i in range(1, N):
        left = drone[i-1]
        right = drone[i]
        if left[1] > right[1]:
            pq.append(Event(right[0]-left[0], left[1]-right[1], i-1, i))

    # 충돌 시간을 기준으로 pq 생성 및 충돌 처리
    heapq.heapify(pq)
    while pq:
        curEv = heapq.heappop(pq)
        curL = curEv.left
        curR = curEv.right

        # 두 드론이 전부 살아있는지 체크
        if isAlive[curL][0] & isAlive[curR][0] != 1:
            continue

        # 충돌 처리
        isAlive[curL][0] = 0
        isAlive[curR][0] = 0

        # 연결 리스트 수정
        curLL = isAlive[curL][1]
        curRR = isAlive[curR][2]
        while curLL != None:
            if isAlive[curLL][0] == 1:
                break
            curLL = isAlive[curLL][1]
        while curRR != None:
            if isAlive[curRR][0] == 1:
                break
            curRR = isAlive[curRR][2]
        if curLL != None:
            isAlive[curLL][2] = curRR
        if curRR != None:
            isAlive[curRR][1] = curLL

        # 충돌 사건 추가
        if curLL != None and curRR != None and drone[curLL][1] > drone[curRR][1]:
            heapq.heappush(pq, Event(drone[curRR][0]-drone[curLL][0], drone[curLL][1]-drone[curRR][1], curLL, curRR))

    # 남은 드론 체크
    count = 0
    leftI = []
    for i in range(N):
        if isAlive[i][0] == 1:
            leftI.append(i+1)
            count += 1

    return [[count], leftI]


def main():
    N = int(input())
    drone = []
    for _ in range(N):
        drone.append(tuple(map(int, input().decode().split())))
    
    for i in solve(N, drone):
        print(*i)


main()