[BOJ] 2610 - 회의준비

이 문제는 두 가지를 알고 있어야 풀 수 있는 문제이다.

Union-Find가 아니라 다른 방법을 사용해서 그룹을 찾아낼 수 있다면 그 방법을 써도 상관없다.

(맞은 사람 코드를 확인해보니 BFS나 DFS 같은걸 쓰신듯 하다)

저 두가지 기법을 사용하는 문제를 몇 개 풀어보긴 했지만, 코드가 잘 기억나지 않아서 복습을 했다. 좋은 연습 문제라고 생각한다.

입력받은 인원수만큼 인접행렬을 만들어 준다음, 간선 데이터를 입력 받아서 dist[i][j] = 1 처리.

이후에 플로이드를 돌려주면 적절하게 처리된 위원회 데이터가 나온다.

문제는 여기서 각 그룹을 찾아서, 해당 그룹의 의사결정시간을 최소로 만드는 아이를 찾아야된다.

주의해야할 점은 다음과 같다.

자기 혼자 그룹인 경우도 있음. (당장 BOJ에 있는 예시만 하더라도 8번은 자기 혼자 그룹이다)
어떤 사람한테 같은 그룹원이 접근하는데 필요한 비용을 모두 더한 값의 최소를 구하는 것이 아니다.
- 예를 들어 [1,2,3]이 한 그룹이고 2번 -> 1번 비용은 3, 3번 -> 1번 비용이 2라고 하면 의사전달시간의 최대값은 3이다.
- 바로 이 최대값이 최소가 되는 대표를 구하는 것. 이 것을 혼동하는 바람에 나도 몇 번이나 제출해서 다 틀렸었다.
각 위원회의 대표 번호를 작은 수 부터 차례로 출력해야한다.

그룹 짓는데 Union-Find를 썼으면, 이제 그 그룹 기반으로 각 dist를 탐색해서 최대값을 구하면 된다.

사실.. 여기까지 해놓고도 몇 번을 더 틀렸는데, 알고보니 내가 구한 배열을 출력 했을 때 작은 수 부터 차례로 출력되지 않았기 때문. 그래서 정렬 한번 돌려주고 출력하니까 맞았다.