백준 2660 자바 - 회장뽑기 (BOJ 2660 JAVA)

문제 : https://www.acmicpc.net/problem/2660

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2660.java

 

  사실상 언어영역 문제였다. '예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.' 대체 이게 뭔 X소리인가 해서 일단 공책에 그래프 그려보고 서로 몇다리 건너뛰어야 하는지 그려보고 생각해보기로 했다.

 

  결론적으로 문제에 제시된 예제1은 다음과 같이 그려진다.

그럼 이걸 간선 가중치 1의 무방향 그래프라 보고 모든 회원에서 회원으로 거리를 재보면 다음과 같다. 즉, 서로 몇다리를 거쳐 친구인지 확인해 보는 것이다.

 

결론적으로 보면, 각 사람마다 모든 사람과 친구과 되기 위해 걸친 다리수의 최대치가 점수인 것을 알 수 있다.

1 : 5번과 3 이므로 3점

2 : 5번과 2 이므로 2점

3 : 1번과 2 이므로 2점

4 : 1번과 2 이므로 2점

5 : 1번과 3 이므로 3점

 

회장 후보는 점수가 가장 낮은 그룹이므로, 2점인 3명 (2,3,4)가 된다.

결국 이렇게 하고보니 맞는말이긴한데, 굳이 저렇게 설명해야 했나 싶다.

 

--

 

아무튼 어차피 회원의 수가 최대 50명이므로 가장 무지성으로 쓰기 좋은 플로이드-와샬 알고리즘을 써서 모든 회원으로 부터 모든 회원으로의 최단 거리를 한방에 구해주면 된다. (O(50^3))

코드의 경우, 20~27 line이 플로이드 와샬 부분이다.