(JAVA) 백준 16681번 : 등산 --- [다익스트라]

www.acmicpc.net/problem/16681

16681번: 등산

 

안녕하세요.

 

solved.ac 골드1 문제로 다익스트라 알고리즘을 사용하여 해결했습니다.

 

 

장장 4시간에 걸쳐 끙끙대다 해결했는데요.

시간초과, 오답 등 여러 실패를 겪었습니다.

 

 

처음에는 1 ~ N까지 for문 순회하면서

각각의 지점을 정상으로 가정했을 때, 다익스트라를 통해 나온 최소 거리를 가지고 등산의 가치를 구했었습니다.

 

하지만 시간초과!

그 이유는 N이 100000일 경우, 다익스트라 알고리즘을 100000번까지 수행할 수 있기 때문이죠.

 

물론, 시간제한은 1초였습니다.

 

 

 

흠.. 그럼 어떻게할까 고민했습니다.

 

다익스트라 알고리즘 횟수를 줄일 방법이 없을까? 하던 중

 

등산의 조건은 시작지점 -> H(정상) 까지는 무조건 증가하는 높이로 만 이동 가능하고, 반대로 H(정상) -> 도착지점 까지는 무조건 감소하는 높이로만 이동 가능하다는 것을 떠올렸습니다.

 

그래!

 

그럼, 다익스트라를 써서

 

1) 시작지점 -> 전 지점 최소 거리 배열을 구하고 (무조건 높이 오름차순)

 

2) 도착지점 -> 전 지점 최소 거리 배열을 구한 다음 (이것도 무조건 높이 오름차순)

 

3) 이 두 배열의 같은 인덱스 원소 값이 초기 설정 값이 아니면 등산이 가능하다는 뜻이니까

 

4) 해당 인덱스의 높이(정상인 인덱스) * e - 두 다익스트라 배열 더한 값 * d

 

5) 해서 나온 최대 값이 겱국 정답이구나!

 

 

했습니다.

 

 

 

하지만, 또 시간초과!

 

여기서 방문 횟수를 줄이기 위해

우선순위 큐에서 poll 했을 때, 그 원소의 지금까지 이동한 거리와 현재 다익스트라 배열의 값과 비교했습니다.

 

왜냐하면, 이미 더 적은 거리로 해당 지점을 방문했던 적이 있기 때문에 굳이 더 큰 거리로 이동해온 원소를 이어갈 필요가 없기 때문입니다.

 

이러한 예외처리를 해주자

 

통과!

 

 

 

매커니즘은 위 내용과 동일합니다.

자세한 부분은 소스코드 참고해주세요.

 

 

이상입니다.

감사합니다!

 

소스코드

---