2617 구슬찾기 {boj} {플로이드워셜}

풀이링크 {PR}

자세한 설명은 플로이드 워셜 알고리즘 - 그래프 모든 정점에서의 최단경로를 참고할 것.

이 문제는 비록 구슬의 무게를 비교한 결과를 제공하지만 다르게 보면 무게관계를 에지로 볼 수도 있기 때문에 그래프 문제로 봐야 한다. 문제의 조건 중 절대로 중간무게가 될 수 없는 구슬을 찾아야 하기 때문에 조건을 잘 생각해봐야 한다.

들어오는 화살표, 나가는 화살표가 과반을 넘으면 절대로 중간무게가 될 수 없다.

여기에서 들어오는/나가는 화살표란, 위상정렬에서의 indegree, outdegree를 뜻하는 것은 아니고, 전체 그래프에서 본인 노드로 향하는/나가는 화살표의 전체 개수를 세는 것이 관건이다.