백준 1446 지름길

https://www.acmicpc.net/problem/1446

1446번: 지름길

예제

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

 

생각

다익스트라로 풀 수 있을 것 같았고, 그래서 가능한 노드,간선,가중치를 모두 찾아 알맞은 그래프로 만드는 것을 목표로 함

 

1) 최대거리는 고속도로 길이 D이다.

2)출발점은(0,0) 도착점은(D,D)이다. 지름길의 길이는 0 이다.

3)  문제에서 "지름길의 시작 위치는 도착 위치보다 작다."라고 되어 있기때문에 시작 위치 또는 도착 위치가 D보다 클 경우 graph 에서 제외 시킨다. - 예제 5번째 줄

4)지름길의 길이가 도착 위치 - 시작 위치 보다 길면 제외시킨다. 더이상 지름길이 아니다. 도착 위치 - 시작 위치 최대 길이이기 때문이다.-예제 6번째 줄

 

이렇게 시작 위치,도착 위치,지름길을 배열에 담았고, 시작 위치를 기준으로 정렬했다. 

정렬된 배열에서 도착 위치가 뒤에 있는 원소들의 시작 위치보다 작으면 graph에 들어가야 하므로 앞의 도착위치, 뒤의 시작위치, 뒤의 시작위치- 앞의 도착위치를 배열에 담았다.

10 60 40
80 90 3

 이렇게 정렬된 배열이 있다면 

10 60 40
80 90 3
60,80,20

을 만들어, 숫자가 연속되게 만들어 고속도로가 끊이지 않게 배열을 만들었다. 이중 for 문을 통해 각 원소당 모든 뒤 배열을 돌아야지만 가능한 모든 경우의 수가 나온다. 지름길의 길이는 각 시작,도착 지점과 상관없기 때문이다. 

배열을 토대로 가능한 노드,간선,가중치를 모두 찾아 알맞은 그래프를 만들어 다익스트라를 사용하여 최단거리를 구했다.

 

제 코드에 질문이 있거나, 개선 방향을 제안해주시면 감사하겠습니다 !

 

코드

import heapq
import sys
INF = sys.maxsize
n,d= map(int,input().split())
dist= [INF for _ in range(d+1)]
graph = [[] for _ in range(d+1)]
arr =[]
pq =[]
arr.append((0,0,0))
arr.append((d,d,0))
for _ in range(n):
    start,end,length = map(int,input().split())
    if start > d or end > d or end-start < length :
        continue
    arr.append((start,end,length))
arr.sort()
for i in range(len(arr)):
    for j in range(i+1,len(arr)):
        if arr[j][0]-arr[i][1]>0:
            arr.append((arr[i][1],arr[j][0],arr[j][0]-arr[i][1]))
for s,e,w in arr:
    graph[s].append((e,w))

def dijkstra(end):
    dist[0] =0
    heapq.heappush(pq,(0,0))
    while pq:
        min_dist, min_index = heapq.heappop(pq)

        if dist[min_index] != min_dist :
            continue

        for target_index,target_dist in graph[min_index]:
            new_dist = min_dist+target_dist
            if dist[target_index] > new_dist:
                dist[target_index] = new_dist
                heapq.heappush(pq,(new_dist,target_index))
    return dist[end]
print(dijkstra(d))

 

 

시도

8일 전에 시도하고 계속 고민하다 오늘 풀었다 120ms 정도 걸리는데 다른 파이썬 유저와 비교해 보면 느린 편에 속한다. 

다익스트라말고 다른 방법으로 시도하면 더 빨리 풀 수도 있을 것 같다. 고민을 더 해봐야겠다.

그래도 끝까지 답 안 보고 포기 안했다.