문제 요약
도로는 수평 또는 수직 선분이며, 교차하거나 만나는 지점에서 서로 연결된다. 각 도로의 중앙에는 제한 속도를 가진 카메라가 있다.
1번 도시에서 출발해 각 도시까지 일정한 속도로 이동할 때, 경로에서 통과하는 모든 카메라 제한 속도를 만족하는 최대 속도를 구한다. 카메라를 전혀 지나지 않는 경로가 있으면 제한 없이 이동할 수 있으므로 0을 반환한다.
핵심 아이디어
1. 도로를 중요한 지점에서 분할해 그래프로 만든다
도로 위에서 이동 방향을 바꾸거나 제한 속도가 발생할 수 있는 지점은 다음과 같다.
- 도로의 양 끝점
- 도시 위치
- 도로의 교차점 또는 접점
- 각 도로 중앙의 카메라 위치
각 도로에 포함된 중요 지점을 도로 방향으로 정렬하고, 이웃한 지점을 간선으로 연결한다. 같은 좌표의 지점은 하나의 그래프 정점으로 합친다.
2. 카메라는 정점 제한으로 처리한다
카메라가 있는 지점을 지나면 제한 속도를 지켜야 한다. 카메라 정점과 연결되는 모든 간선의 제한 속도를 해당 카메라 제한 속도 이하로 설정하면, 그 정점을 통과하는 모든 경로에 제한을 적용할 수 있다.
한 좌표에 카메라가 여러 개라면 가장 낮은 제한 속도를 사용한다.
3. Widest Path를 사용한다
어떤 경로로 이동 가능한 최고 일정 속도는 그 경로에서 만나는 간선 제한 속도의 최솟값이다. 도시마다 이 최솟값을 최대화해야 하므로 최단 경로가 아니라 Widest Path 문제다.
다익스트라와 같은 방식으로 우선순위 큐를 사용하되, 거리가 작은 정점 대신 현재까지의 제한 속도가 큰 정점을 먼저 꺼낸다.
next_speed = min(current_speed, edge_limit)Python 코드
from heapq import heappop, heappush
def solution(city, road):
INF = 10**18
road_count = len(road)
# (x1, y1, x2, y2, limit) 형태로 도로를 저장한다.
roads = [tuple(info) for info in road]
road_points = [[] for _ in range(road_count)]
camera_limit = {}
def is_horizontal(current_road):
return current_road[1] == current_road[3]
def contains(current_road, x, y):
x1, y1, x2, y2, _ = current_road
return x1 <= x <= x2 and y1 <= y <= y2
def add_point(road_index, point):
road_points[road_index].append(point)
# 도로의 끝점과 중앙 카메라 위치를 추가한다.
for index, (x1, y1, x2, y2, limit) in enumerate(roads):
add_point(index, (x1, y1))
add_point(index, (x2, y2))
camera = ((x1 + x2) // 2, (y1 + y2) // 2)
add_point(index, camera)
camera_limit[camera] = min(camera_limit.get(camera, INF), limit)
# 도시가 포함된 모든 도로에 도시 위치를 분할 지점으로 추가한다.
for x, y in city:
for index, current_road in enumerate(roads):
if contains(current_road, x, y):
add_point(index, (x, y))
# 모든 도로 쌍의 교차점 또는 접점을 찾는다.
for first in range(road_count):
x1, y1, x2, y2, _ = roads[first]
first_is_horizontal = is_horizontal(roads[first])
for second in range(first + 1, road_count):
a1, b1, a2, b2, _ = roads[second]
second_is_horizontal = is_horizontal(roads[second])
point = None
if first_is_horizontal != second_is_horizontal:
horizontal = roads[first] if first_is_horizontal else roads[second]
vertical = roads[second] if first_is_horizontal else roads[first]
hx1, hy, hx2, _, _ = horizontal
vx, vy1, _, vy2, _ = vertical
if hx1 <= vx <= hx2 and vy1 <= hy <= vy2:
point = (vx, hy)
elif first_is_horizontal and y1 == b1:
left = max(x1, a1)
right = min(x2, a2)
if left == right:
point = (left, y1)
elif not first_is_horizontal and x1 == a1:
bottom = max(y1, b1)
top = min(y2, b2)
if bottom == top:
point = (x1, bottom)
if point is not None:
add_point(first, point)
add_point(second, point)
# 동일 좌표를 하나의 그래프 정점으로 합친다.
point_to_index = {}
def get_index(point):
if point not in point_to_index:
point_to_index[point] = len(point_to_index)
return point_to_index[point]
# 먼저 모든 중요 지점에 그래프 번호를 부여한다.
for points in road_points:
for point in points:
get_index(point)
graph = [[] for _ in range(len(point_to_index))]
# 각 도로의 이웃한 중요 지점을 연결한다.
for index, points in enumerate(road_points):
current_road = roads[index]
if is_horizontal(current_road):
ordered_points = sorted(set(points), key=lambda point: point[0])
else:
ordered_points = sorted(set(points), key=lambda point: point[1])
for left, right in zip(ordered_points, ordered_points[1:]):
# 카메라 정점을 지나기 위해 지켜야 하는 가장 낮은 제한 속도
limit = min(
camera_limit.get(left, INF),
camera_limit.get(right, INF),
)
left_index = get_index(left)
right_index = get_index(right)
graph[left_index].append((right_index, limit))
graph[right_index].append((left_index, limit))
start = get_index(tuple(city[0]))
best_speed = [-1] * len(graph)
best_speed[start] = INF
heap = [(-INF, start)]
# 제한 속도가 큰 경로부터 확정하는 Widest Path 탐색
while heap:
negative_speed, current = heappop(heap)
current_speed = -negative_speed
if current_speed < best_speed[current]:
continue
for next_node, limit in graph[current]:
next_speed = min(current_speed, limit)
if next_speed > best_speed[next_node]:
best_speed[next_node] = next_speed
heappush(heap, (-next_speed, next_node))
answer = []
for x, y in city[1:]:
speed = best_speed[get_index((x, y))]
answer.append(0 if speed == INF else speed)
return answer정당성 설명
그래프의 정점은 도시, 도로 끝점, 교차점, 카메라 위치를 모두 포함한다. 따라서 실제 도로에서 이동 방향을 바꾸거나 카메라 제한이 적용될 수 있는 모든 지점이 그래프에 표현된다. 각 도로에서 이웃한 중요 지점을 연결했으므로 그래프의 경로와 실제 도로 이동 경로는 서로 대응한다.
카메라 정점에 인접한 간선의 제한 속도는 그 지점의 최소 카메라 제한 속도 이하로 설정했다. 그러므로 그래프 경로의 최소 간선 제한 속도는 실제 이동 경로에서 지켜야 하는 가장 낮은 카메라 제한 속도와 같다.
Widest Path 탐색은 현재까지 확보한 제한 속도가 가장 큰 정점을 먼저 처리한다. 어떤 도시를 향하는 경로의 값은 경로 간선 제한 속도의 최솟값이며, 전이식 min(current_speed, edge_limit)은 이 값을 정확히 계산한다. 더 큰 값이 발견될 때만 갱신하므로, 최종 best_speed는 1번 도시에서 각 정점으로 갈 수 있는 최고 일정 속도다.
따라서 카메라를 지나지 않는 경우에는 INF를 0으로 바꾸고, 그 외에는 best_speed를 반환하면 요구한 답을 얻는다.
복잡도 분석
도로 수를 M, 중요 지점과 그래프 간선 수를 각각 V, E라고 하자.
- 도시를 도로에 추가:
O(N * M) - 도로 교차점 검사:
O(M^2) - 도로별 지점 정렬:
O(V log V) - Widest Path 탐색:
O((V + E) log V)
전체 시간 복잡도는 O(M^2 + (V + E) log V)이며, 공간 복잡도는 O(V + E)다.
주의할 점
- 도로가 교차하는 좌표뿐 아니라, 도시와 카메라 위치에서도 도로를 분할해야 한다.
- 같은 카메라 위치에 여러 도로의 카메라가 겹치면 제한 속도는 최솟값을 사용한다.
- 카메라를 지나지 않는 경로는 제한 속도가 없으므로 내부적으로 큰 값
INF로 표현한 뒤 최종 결과에서0으로 바꾼다. - 최단 거리 다익스트라와 달리, 우선순위 큐에서는 현재 제한 속도가 큰 상태를 먼저 꺼낸다.
마무리
기하 문제처럼 보이지만 도로를 교차점과 특수 지점에서 분할하면 그래프 문제가 된다. 이후에는 경로의 최소 제한 속도를 최대화하는 Widest Path를 적용해 도시별 최고 일정 속도를 구할 수 있다.
