(JAVA) 백준 1446번 : 지름길 --- [다익스트라]

www.acmicpc.net/problem/1446

1446번: 지름길

 

안녕하세요.

 

다익스트라 문제입니다.

 

 

제가 처음에 생각한 해결 방법은

 

모든 지름길을 찾아서 다익스트라로 지름길의 도착지점의 값을 변경한 후

 

각 지름길 도착 지점 + 도착 지점까지의 남은 거리 의 최소를 찾으려고 했습니다만

 

 

예외 케이스가 있었나봅니다..

 

결과는 틀렸습니다.

 

 

그래서 해설을 조금 참고했습니다.

 

 

맙소사!

 

다르게 생각하니, 쉽게 해결할 수 있는 것을...

 

 

그건 바로, 거리를 시작 지점에서 1씩 이동하면서 각 지점에 대해 다익스트라 처리를 하면 되는 것입니다.

 

 

그래서 1씩 이동하면서

 

그 지점에 지름길이 있다면 해당 지점에서 지름길을 타고 도착하는 경우와 현재 다익스트라 배열에 저장된 값과 비교해서 최솟값으로 갱신해줍니다.

 

그 지점에 지름길이 없다면 이전 지점 + 1 과 현재 지점의 다익스트라 배열에 저장된 값을 비교하여 최솟값으로 갱신해줍니다.

 

이를 목적지까지 이동하면서 진행하고, 목적지의 다익스트라 배열 값을 출력하면 끝!

 

 

이상입니다.

 

감사합니다.

 

 

 

소스코드

---