[BOJ] 2610 - 회의준비


BOJ 2610 - 회의준비

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

  • Floyd-Warshall
  • Union-Find

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

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

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

접근 방법

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

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

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

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

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

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

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

전체 코드