[BOJ 9083] 셔틀버스 Python

BOJ 9083 셔틀버스

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

골드4가 골드4 문제 풀기😎

이 문제는 버스 스케줄링 문제를 다루고 있다. 구체적으로는 학교와 터미널 사이를 운행하는 버스들을 최소한의 버스로 운영하는 문제이다.

풀이 과정

이 문제는 '그리디 알고리즘'을 이용하는 문제로, 그리디 알고리즘은 매 순간에 가장 좋은 선택을 하는 알고리즘이다. 전체 문제의 최적해를 고려하지 않고, 현재 상황에서 가장 유리한 선택을 계속해서 최종 답을 구하는 방식이다.

그 특징으로는 아래의 특징이 있다:
1. 근시안적 선택: 현재 상황에서만 최선의 선택
2. 선택의 되돌림 불가: 한 번 선택하면 바꾸지 않음
3. 빠른 실행: 보통 O(nlogn) 정도의 시간 복잡도

이 문제는 "사용 가능한 버스가 여러 대 있을 때, 가장 늦게 도착한 버스를 재사용"하는 방식으로 그리디 알고리즘을 활용한다.

이 문제를 풀기 위한 사고 과정은 아래와 같다.
1. 학교(S)와 터미널(T)를 구분하여 정렬된 전체 버스 시간 리스트 생성
2. 학교와 터미널에 만약 사용 가능한 버스가 있다면 버스를 재사용하면 되기에, 학교와 버스에 각각 리스트 생성
3. 사용 가능한 버스가 있다면 사용 가능한 버스 중 가장 늦게 도착한 버스를 이용하고, 그렇지 않다면 새로운 버스를 이용

위와 같이 세 가지 논리적 단계를 이해한다면, 문제를 풀 수 있을 것이다.
코드는 아래와 같다.

import sys
from datetime import datetime, timedelta
import heapq

input = sys.stdin.readline
T = int(input())

for _ in range(T):
    D = int(input()) 
    A = int(input())
    bus=[]
    for _ in range(A):
        tmp = datetime.strptime(input().strip(), '%H:%M')
        bus.append((tmp, 'S',tmp+timedelta(minutes=D)) )
    B = int(input())
    for _ in range(B):
        tmp = datetime.strptime(input().strip(), '%H:%M')
        bus.append((tmp, 'T',tmp+timedelta(minutes=D)) )

    bus.sort(key=lambda x: x[0])

    school = []   
    terminal = [] 
    cnt=0

    for time, bus_type, ready_time in bus:
        if bus_type == 'S':
            temp = []
            while school and school[0] <= time:
                temp.append(heapq.heappop(school))
            if temp:
                temp.remove(max(temp))
                for t in temp:
                    heapq.heappush(school, t)
            else:
                if terminal and terminal[0] + timedelta(minutes=D) <= time:
                    heapq.heappop(terminal)
                else:
                    cnt += 1
            heapq.heappush(terminal, ready_time)
        else: 
            temp = []
            while terminal and terminal[0] <= time:
                temp.append(heapq.heappop(terminal))
            if temp:
                temp.remove(max(temp))
                for t in temp:
                    heapq.heappush(terminal, t)
            else:
                if school and school[0] + timedelta(minutes=D) <= time:
                    heapq.heappop(school)
                else:
                    cnt += 1
            heapq.heappush(school, ready_time)

    print(cnt)


    

회고

문제를 푸는데 생각보다 오래 걸렸다.
코드가 맞아 보이는데, 이유를 모르게 채점 현황에서 25%가 되면 실패가 발생했다.
도저히 원인을 못 찾겠어서 질문게시판에 들어가보았고, 엣지 케이스를 발견했다.

1. 학교에서 출발하는 버스에 대해 판단을 진행할 때, 만약 학교에서 09:00 출발이라면, 터미널에서 이용 가능한 버스 중 09:00까지 학교에 도착할 수 있다면 버스를 재사용 가능하다.
2. 이용 가능한 버스가 여러 대 있다면, 그 버스 중 가장 최근에 도착하는 버스를 이용하는 것이 '그리디 알고리즘'에 적합한 논리이다.

이 두 가지 경우에 대해 생각을 하지 못했다.

즉, 아래와 같이 세 단계를 거치면 되는 것이다.
1. 현재 위치에서 이용 가능한 버스 중 가장 늦게 도착한 버스 재이용
2. 현재 위치에 이용 가능한 버스가 없다면, 반대편에서 이용 가능한 버스 중, 출발 시간까지 도착 가능한 버스를 재이용
3. 위의 케이스 모두 사용가능한 버스가 없다면 새로운 버스 이용

이렇게 적용하면 엣지 케이스를 처리 할 수 있다.

휴... 알고리즘 꾸준히 풀어야겠다.
그래도 이번에 오랜만에 알고리즘 풀면서 잊고 있었던 datetime, heapq 모듈도 다시 써볼 수 있어서 좋았다.