Problem Solving/BOJ
2610. 회의준비
해스끼
2020. 11. 13. 11:54
오랜만에 문제 풀이를 쓴다. 요즘 바빠서;;
2610번: 회의준비
첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이
www.acmicpc.net
위원회 구성
우선 위원회를 구성해야 한다. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 하므로, Union-Find를 이용하여 위원회를 구성할 수 있다. 서로 알고 있는 사람끼리 ``merge``한 다음, 각 참석자 ``i``를 ``root(i)`` 쪽으로 모은다.
대표 결정하기
대표를 결정하려면 우선 두 사람 사이의 의사전달시간을 알아야 한다. 매번 BFS 등으로 탐색하면 매우 비효율적이므로, 플로이드-와샬 알고리즘을 사용하여 임의의 두 사람 사이의 의사전달시간을 미리 계산해 두자.
그 후에는 의사전달시간의 최댓값이 최소가 되도록 하는 대표를 찾으면 된다. 간단하죠?
주의! 의사전달시간의 합이 최소가 되도록 하면 안 된다.

깔끔.