[ 1446 ] [ BFS ] 지름길

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

1446번: 지름길

 

---

풀이 과정

---

1. 지름길 데이터를 정리한다.
   
   1. 시작점과 도착점이 같은데 이동 거리가 다른 지름길이 있을 수 있으므로 최소 거리로 해주어야 한다.
   2. 최소 거리로 조정한 다음, 딕셔너리를 사용하여 [시작점] = [[도착점, 이동거리], ... ] 형식으로 데이터를 저장한다. 
2. BFS를 진행한다.
   1. 시작점과 이동거리를 a, b라고 할 때, 두가지 경우가 존재한다. 
   2. 현재 지점의 다음 지점을 큐에 삽입한다. (a+1, b+1)
   3. 만약 현재 지점에 대응하는 키가 딕셔너리에 존재한다면(지름길이 존재한다면) 지름길로도 이동해보면 된다. (도착점, b+지름길 이동 거리)
   4. 현재 지점이 D라면, 정답을 갱신시켜 준다. 이 때 유의할 점은, 일방통행이므로 D를 넘게 되면 정답 처리가 되지 않음에 유의한다.
3. 정답을 출력한다.

문제의 분류는 다익스트라 알고리즘이었으나.. 처음 떠오른 방식이 BFS라 BFS로 풀이함. BFS가 아니더라도 다익스트라 알고리즘이나 DP로도 풀수 있다고 생각한다.

 

---

소스 코드

---

import sys
from collections import defaultdict, deque

input = lambda : sys.stdin.readline().rstrip()

N, D = map(int, input().split())
temp = defaultdict(lambda:int(10e9))

for _ in range(N):
    s, e, d = map(int, input().split())
    temp[(s, e)] = min(temp[(s, e)], d)

shortcut = defaultdict(lambda:[])
for (s, e), d in temp.items():
    shortcut[s].append([e, d])

queue = deque()
queue.append([0, 0])

answer = int(10e9)
while queue:
    current, movement = queue.popleft()
    if current > D:
        continue
    if current == D:
        answer = min(answer, movement)
        continue
    if shortcut.get(current) != None:
        for e, d in shortcut[current]:
            queue.append([e, movement + d])    
    queue.append([current+1, movement+1])
    
print(answer)