[BOJ] 백준 1976 여행 가자 (JAVA)

플로이드워셜 응용

📑 문제

백준 1976 여행 가자

---

🌱 아이디어

여행계획이 주어질 때 A -> B 도시로 갈 수 있는 경로가 있는지 판단하는 문제!

 

우리가 만약 A에서 B 도시로 이동해야 한다면 두 가지 경우가 있을 것이다.

 

1. A -> B (직행 경로)

2. A -> C -> B (경유 경로)

 

즉 직행을 못하는 경우는 어떠한 "도시"를 경유해서 목적지로 도착해야 한다. 이런 경우 경유하는 도시를 기준으로

최단거리를 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용하면 쉽게 풀 수 있다.

 

하지만 이 문제는 최단거리를 구할 필요가 없고 갈 수 있는 도시인지를 판단만 하면 되기 때문에 살짝(?)만

응용해서 플로이드-워셜 알고리즘을 구현하면 풀 수 있다.

---

🌱 코드 및 풀이

 

플로이드 워셜 알고리즘에서 최단거리가 아닌 "경로존재 여부"를 판단하는 것 이기 때문에

경유 도시를 기준으로 A -> 경유도시 -> B 가 가능하다면 인접배열에  '1'을 표시하는 것을 반복하고

 

여행계획에 문제가 있는지 없는지를 판단해서 출력하면 된다.

---

🌱 느낀 점

 

플로이드 워셜 알고리즘을 원래 알고 있었기 때문에 쉽게 구현했던 문제이다! 크게 어려운 부분은 없었으나

사소한 오타 때문에 7번 정도 틀렸다;; 틈틈이 복습해야 실수를 줄일 수 있을 것 같다 ㅎㅎ

 

문제 유형중 경로를 묻거나 어딘가를 거쳐가야 한다는 유형이 있다면 플로이드워셜 알고리즘을 떠올리자! 끝~