[BOJ] 백준 1719 택배 (JAVA)

최단거리+경로추적

📑 문제

백준 1719 택배

---

🌱 아이디어

최단거리를 구하고, 최단거리 루트의 경로 역추적을 통해 풀어보자!

 

최단거리 문제이다. 하지만 최단거리로 갈 때 바로 첫 노드를 출력하는 문제이다.

 

가령 1 → 5번 노드로 가야 한다면 여러 가지 루트 중 가장 최단 경로 1 → “3” → 4 → 5 일 때

위 문제에서 요구하는 답은 "3"번 노드를 출력하는 게 조건이다.

 

즉 경로 역추적 알고리즘이 필요하다.

 

그리고 또 하나 i → j로 갈 때 바로 직행하는 방법도 있지만 이러한 루트는 최단루트가 아닐 수 있다.

i → j ,  i → h → j ⇒ 직행루트 와 경유지가 있는 루트를 비교해야 한다

결국 플로이드워셜 알고리즘을 사용하는 게 가장 좋아 보이는 문제이다.

기본적인 플로이드 워셜 알고리즘을 구현하는 것은 어렵지 않았으나. 경로 역추적 + 경로 중 출발지에서 도착한 첫 노드를 출력해야 하기 때문에 고민을 좀 했다.

 

최대한 단순하게 생각해서 출력을 완성시켰다 총 3단계가 있다.

 

• 1번 경우 → i ==j 인경우 “-” 출력
• 2번 경우 → i → j 직행 루트 경우 “도착노드(j)” 출력
• 3번 경우 → i → fw → j 경유지루트 경우 출발노드 (i)에 도착하기 “전 노드 출력”

1번, 2번은 어렵지 않다 3번 경우는 역추적을 응용을 해야 하기 때문에 어려울 수 있어서 그림을 준비했다.

 

 

경로 역추적 원리

• 0 → 6까지 최단 루트 0 → 2 → 4 → 6인 경우 (그림)

위 경우 순서는 arr1 [6] = 4 ⇒ arr1 [4] = 2 ⇒ arr1 [2] = 0 ⇒ arr1 [0] = -1 이렇게 진행된다

 

만약 val = -1이라면  바로 그전 노드인 "2번 노드"를 출력하면 된다.

 

---

🌱 코드 및 풀이

 

---

🌱 느낀 점

 

골드 3 문제도 한 번에 풀만큼 실력향상이 느껴진다. 사실 경로 역추적 알고리즘은 이해하기 어려워서

직접 그려가면서 공부했는데 도움이 된 것 같다 ㅎㅎ

 

이해가 안 될 때 눈으로 직접 볼 수 있게 그려보면서 코드검증을 하는 게 도움이 가장 많이 된다

빨리 골드문제에 익숙해질 수 있게 더 노력해야겠다