[백준 2660번] 회장뽑기 (java)

BOJ

lotus lee 2021. 3. 2. 21:31

2660번: 회장뽑기

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터

www.acmicpc.net

문제를 보자마자 플로이드 워셜 알고리즘이 떠올랐다.

어느 회원과 다른 회원과의 점수는 노드 사이의 거리라고 생각할 수 있다.

어느 회원 노드에 대해서 다른 모든 회원 노드와의 거리를 구하고, 그 중에서 가장 큰 거리가 그 회원의 점수가 된다.

모든 회원에 대하여 다른 회원과의 거리를 알아야 하므로 플로이드 워셜 알고리즘을 사용하면 된다.

예를 들어, 문제의 예제에서 1번 회원은 2,3,4,5번 회원과의 거리가 각각 1, 2, 2, 3 이다.

이 중에서 가장 큰 값이 1번 회원의 점수가 되므로 1번 회원의 점수는 3이 된다.