회장 뽑기

문제 설명 풀이 코드 플로이드 와샬 알고리즘의 개념과 동작 방식만 이해했다면 쉽게 접근할 수 있는 문제인 듯하다. 플로이드 와샬 (Floyd-Warshall) 서론 자주 다익스트라와 함께 언급되는 알고리즘으로, 모든 정점에서 다른 모든 정점까지의 최단 거리를 구... blog.naver.com 해당 알고리즘은 모든 정점에서 다른 모든 정점까지의 거리를 구하는 알고리즘이다.

그리고 이 문제는 친구의 친구의 ··· 친구, 연관 거리가 적은 사람을 찾아 회장 후보로 올리는 문제이다. 예를 들어 위 사진에서 1과 5랑 연관된 노드는 2, 3나 2, 4, 3로 연관 거리는 5를 포함한 3이나 4이다.

그리고 문제에서 찾는 것은 이러한 연관거리가 제일 적은 사람이므로, 플로이드 와샬을 통해 모든 회원에서 회원으로 이어지는 최소 연관 거리를 찾아내면 된다. for (int k=1; k<=n; ++k) for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) fri...