(JAVA) 백준 1613번 : 역사 --- [플로이드 - 와샬]

https://www.acmicpc.net/problem/1613

1613번: 역사

 

안녕하세요.

 

플로이드 - 와샬 알고리즘 사용하는 문제입니다.

 

 

정답률이 낮은 이유는 

 

쉽게 헷갈릴 수 있는 부분이 있어서 인데요.

 

 

우선, 벨만포드 알고리즘에서 중요한 for문 부분을 보시면

 

맨 처음 for문은 경유 지점, 다음 for문은 출발 지점, 마지막 내부 for문은 도착 지점 을 가리킵니다.

 

 

그리고,  A -> B , B -> C 이면 A -> C 라는 명제같은 논리를 반영해야 합니다.

 

마지막으로, 실제 검증할 때 

 

A -> B

B -> A

여부를 전부 체크해야 합니다.

 

둘 다 false 이면 알 수 없음

A -> B 만 true 이면 -1

B -> A 만 true 이면 1

 

이렇게 되는 것이죠.

 

 

이상입니다. 자세한 사항은 하단 소스코드를 참고해주세요!

 

감사합니다!

 

 

소스코드

---