백준 2660번 [회장뽑기](C++) -yes6686- 티스토리

백준 문제 풀이: 2660 [회장뽑기]

---

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

문제 설명:

각 회원 간의 관계를 그래프로 표현하여, 회원들 간의 가장 짧은 거리를 계산한 후 각 회원의 최대 거리(점수)를 구합니다. 이 점수 중 가장 작은 값을 갖는 회원들이 회장 후보가 되며, 후보들의 수와 번호를 출력합니다.

---

문제 해결 코드

// 백준 2660 - 회장뽑기
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9; // 무한대를 표현

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<vector> graph(n + 1, vector(n + 1, INF));

    // 관계 입력
    while (true) {
        int a, b;
        cin >> a >> b;
        if (a == -1 && b == -1) break;
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    // 플로이드-워셜 알고리즘으로 모든 회원 간 최단 거리 계산
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }

    // 각 회원의 점수 계산
    vector scores(n + 1);
    int minScore = INF;

    for (int i = 1; i <= n; i++) {
        int maxDistance = 0;
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                maxDistance = max(maxDistance, graph[i][j]);
            }
        }
        scores[i] = maxDistance;
        minScore = min(minScore, maxDistance);
    }

    // 회장 후보 찾기
    vector candidates;
    for (int i = 1; i <= n; i++) {
        if (scores[i] == minScore) {
            candidates.push_back(i);
        }
    }

    // 결과 출력
    cout << minScore << " " << candidates.size() << '\n';
    for (int candidate : candidates) {
        cout << candidate << " ";
    }
    cout << '\n';

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 플로이드-워셜 알고리즘: 모든 노드 간의 최단 거리를 계산합니다.
• 구현 세부사항:
  • 초기화: 모든 회원 간의 거리를 무한대로 설정합니다.
  • 입력 관계를 반영하여 양방향 거리를 1로 설정합니다.
  • 플로이드-워셜 알고리즘을 통해 최단 거리 계산을 수행합니다.
  • 각 회원의 최대 거리를 계산하여 점수를 결정합니다.
  • 가장 낮은 점수를 가진 회원들을 후보로 선정합니다.
• 시간 복잡도 분석:
  • 플로이드-워셜 알고리즘: O(n³)
  • 최종 점수 계산 및 후보 찾기: O(n²)
  • 총 시간 복잡도: O(n³)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!