[BOJ 2660] 회장뽑기

2660번: 회장뽑기

1. 문제 설명

 

예제 1에서 1번부터 5번 회원의 점수는 각각 3점, 2점, 2점, 2점, 3점이다.

그러므로 가장 작은 점수는 2점이 되고, 점수가 2점인 2, 3, 4번 회원 총 3명이 회장 후보가 되는 것이다.

 

2. 구현 아이디어 1 - 틀렸습니다.

1. 현재 노드에서 가장 거리가 먼 노드까지의 거리가 해당 회원의 점수가 된다.
2. 모든 회원의 점수를 배열에 저장하고, 배열의 최솟값(=score)을 찾는다.
3. 값이 score인 원소의 index를 candidate라는 배열에 저장한다.
4. 첫째 줄에는 score와 candidate 배열의 길이를 출력한다.
5. 둘째 줄에는 candidate 배열의 원소를 순서대로 출력한다.

 

1번을 구현하기 위해 DFS를 사용했다.

 

#include <bits/stdc++.h>

using namespace std;

int n; // 회원의 수
map<int, vector<int>> mp; // 인접 그래프
int a, b;

void dfs(map<int, vector<int>> &mp, vector<int> &arr, int start) {
    // 초기화
    stack<pair<int, int>> s;
    vector<bool> visited(n+1);

    // 시작 노드 삽입
    s.push({start, 0});
    visited[start] = true;

    while (!s.empty()) {
        int cur = s.top().first;
        int cScore = s.top().second;
        if (cScore > arr[start]) arr[start] = cScore;
        s.pop();

        for (auto node : mp[cur]) {
            if (visited[node]) continue;

            s.push({node, cScore + 1});
            visited[node] = true;
        }
    }
}

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

    cin >> n;
    while (true) {
        cin >> a >> b;
        if (a == -1 && b == -1) break;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }

    vector<int> arr = vector<int>(n+1);
    arr[0] = INT_MAX;
    for (int i = 1; i < n+1; ++i) {
        dfs(mp, arr, i);
    }

    int score = *min_element(arr.begin(), arr.end());
    int ret = 0;
    vector<int> candidate;

    for (int i = 1; i < n+1; ++i) {
        if (arr[i] == score) {
            ret ++;
            candidate.push_back(i);
        }
    }

    cout << score << " " << ret << "\n";
    for (auto elem : candidate) {
        cout << elem << " ";
    }

    return 0;
}

 

반례
5
1 2
2 3
3 4
4 5
5 1
-1 -1

 

위와 같은 입력이 들어올 경우 3번과 4번 노드의 점수는 2점이지만, if(cScore > arr[start]) arr[start] = cScore; 이라는 부분 때문에 무조건 더 큰 3이 저장된다.

 

3. 구현 아이디어 2 - 맞았습니다 !!

DFS 코드를 보완해서 문제를 풀 수도 있지만 해당 문제를 플로이드-와샬 알고리즘으로도 풀 수 있다는걸 알고 플로이드-와샬 알고리즘을 사용하여 문제를 다시 풀었다.

 

n의 최댓값이 50으로 크지 않기 때문에 3중 반복문을 사용하여도 제한 조건 내에서 문제를 풀 수 있다.

 

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321
int n; // 회원의 수
vector<vector<int>> arr = vector(51, vector<int>(51, INF));
int a, b;

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

    cin >> n;
    while (true) {
        cin >> a >> b;
        if (a == -1 && b == -1) break;
        arr[a][b] = 1;
        arr[b][a] = 1;
    }

    for (int k = 1; k < n+1; ++k) {
        for (int i = 1; i < n+1; ++i) {
            for (int j = 0; j < n+1; ++j) {
                if (i == j) arr[i][j] = 0;
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
            }
        }
    }

    vector<int> candidate = vector<int>(n+1);
    for (int i = 1; i < n+1; ++i) {
        for (int j = 1; j < n+1; ++j) {
            if (arr[i][j] > candidate[i]) candidate[i] = arr[i][j];
        }
    }

    int score = INF;
    vector<int> ret;

    // 회장 후보의 점수 계산
    for (int i = 1; i < n+1; ++i) {
        if (candidate[i] < score) score = candidate[i];
    }

    // 회장 후보 계산
    for (int i = 1; i < n+1; ++i) {
        if (candidate[i] == score) {
            ret.push_back(i);
        }
    }

    cout << score << " " << ret.size() << "\n";
    for (auto elem : ret) {
        cout << elem << " ";
    }
    
    return 0;
}