[BOJ] 1446 지름길 Python

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

1446번: 지름길

지름길

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

6099

3171

2411

51.561%

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

 

풀이 코드 (정답 참고)

import sys
input = sys.stdin.readline

n, d = map(int, input().split())
# 초기 고속도로로 갈 때의 거리
dis = [i for i in range(d+1)]
shortcuts = []
for _ in range(n):
    s, e, shortcut = list(map(int, input().split()))
    shortcuts.append([s, e, shortcut])

for i in range(d+1):
    # 고속도로와 지름길 길이 비교
    dis[i] = min(dis[i], dis[i-1]+1)

    for s, e, shortcut in shortcuts:
        if i==s and e<=d and dis[i]+shortcut < dis[e]:
            dis[e] = dis[i]+shortcut

print(dis[d])

정답 코드를 참고했다.

풀이 알고리즘

- bfs 탐색으로 문제를 수행한다.

- 0부터 고속도로의 길이까지 반복하여 최단 거리를 구한다.

- 지름길로 간 거리와 고속도로로 간 거리를 비교하여 최단 거리를 입력한다.

- 지름길을 반복하여 최단 거리를 찾는다.

 

d 최대 값이 10000이기 때문에 노드 하나하나로 구하면 된다.

다익스트라, dp 기본문제를 더 풀고 시간복잡도에 대해서 더 공부해야겠다.