[BOJ] 백준 14938 서강그라운드 (JAVA)

그래프 탐색은 즐거워!

📑 문제

---

🌱  아이디어

N 번 반복 다익스트라알고리즘과 플로이드 워셜 알고리즘 두 방법으로 풀 수 있다

일단 나는 다익스트라 알고리즘을 사용해서 풀기로 했다 (그냥 빠를 것 같아서...) 사실 플로이드 워셜을 사용해도 시간초과는 걱정

안 해도 된다 ㅎㅎ

위 문제에서 "탐색 범위"를 입력으로 주는데, 예를 들어 탐색 범위가 5 일 때 현재 노드로부터 다른 노드까지의 거리가

5보다 작거나 같아야 한다. 즉 현재 노드에서 모든 노드의 최단거리를 구하고, 탐색범위 이하의 노드들의 아이템을 도출한다!

 

---

🌱 코드 및 풀이

그래프가 가지는 모든 정점을 기준으로 각각 시작노드로 설정 후 모든 정점을 기준으로 최단거리를 탐색하고

탐색범위에 비례한 아이템을 챙길 수 있는 최대 숫자를 출력한다.

 

즉 현재 노드에 아이템이 몇 개가 있는지 알아야 하기 때문에 res 배열을 만들어 i 번 노드의 아이템 수를 입력했다.

 

위 코드가 입력받는 부분이 길어서 복잡해 보이지만 다익스트라 부분을 중점적으로 보면 이해하기 편할 것이다.

최단거리 알고리즘만 알면 쉽게 풀 수 있는 문제인 것 같다.

 

---

🌱 느낀 점

자바 기준 in 100등!

플로이드와 다익스트라 두 알고리즘을 다 사용해 봤지만 시간복잡도도 낮고 범용성이 넓은 건 다익스트라 인 것 같다

다익스트라를 이해하기 힘들었지만, 이해하고 나니 골드 4-5 최단거리 문제들은 쉽게 풀 수 있게 된 것 같다 ㅎㅎ 끝!