(JAVA) 백준 14938번 : 서강그라운드 --- [다익스트라]

www.acmicpc.net/problem/14938

14938번: 서강그라운드

 

 

안녕하세요.

 

다익스트라 알고리즘 문제 리뷰합니다.

 

해당 문제는 어렵지 않았습니다!

 

 

단, 저도 헷갈렸던 부분이 있습니다.

 

 

밑줄 친 부분에서, 수색 범위 값은 m , 길의 개수는 r 입니다!!!

(조건 값을 r로 했다가 왜틀렸는지 몰랐...)

 

 

바로 솔루션 설명하겠습니다.

 

솔루션

---

  -  우선, 양방향 그래프입니다.

 

  -  다익스트라 결과값 배열은 시작 지점부터 해당 지점까지 이동하는 최소 거리 입니다.

 

  -  그럼 결과값 배열을 어디서 쓰냐?

    ->  해당 지점까지 이동한 최소 거리가 수색 범위인지 확인해서, 수색 범위 이내 값이라면 해당 지점까지 수색이 가능하단 뜻입니다.

 

  -  다익스트라 결과값 배열을 한 바퀴 순회하면서, 수색 범위 이내인지 체크하여 수색 범위 이내인 경우 해당 지점의 아이템 개수를 더합니다.

 

  -  이렇게 더한 누적합 값이 즉, 얻을 수 있는 최대 아이템 개수 입니다. (정답이란 뜻)

 

 

간단하죠?

 

이상입니다.

 

감사합니다!

 

 

 

소스코드

---