백준 2660 - 회장뽑기(C++)

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

2660번: 회장뽑기

BFS를 이용한 문제입니다.

친구 사이가 얼마나 떨어져있나에 따라 점수가 달라집니다.

모든 사람과 친구 사이이면 1점, 친구의 친구 사이가 있다면 2점, 친구의 친구의 친구 사이가 있다면 3점이 됩니다.

즉, BFS 탐색을 할 때, 탐색의 깊이만큼 사람의 점수가 된다는 의미입니다.

 

1번 사람부터 N번 사람까지 각각 탐색을 해줘야합니다.

그러면, 1~N번 사람까지 자신의 점수가 구해질 것입니다.

이를 비교해 값을 출력해주면 됩니다. 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define INF 987654321;

using namespace std;

int N;
vector<int> connect[51];
int check[51];
int Friend[51];
vector<int> node;

void bfs(int start){
    memset(check, 0, sizeof(check));
    queue<int> q;
    q.push(start);
    check[start] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] != 0) continue;
            check[xx] = check[x] + 1;
            q.push(xx);
        }
    }
    for(int i = 1; i <= N; i++){
        if(i == start) continue;
        if(Friend[i] < check[i] - 1) {
            Friend[i] = check[i] - 1;
        }
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        bfs(i);
    }
    int maxi = INF;
    for(int i = 1; i <= N; i++){
        if(Friend[i] < maxi){
            maxi = Friend[i];
            node.clear();
        }
        if(Friend[i] == maxi){
            node.push_back(i);
        }
    }
    cout << maxi << " " << node.size() << "\n";
    for(int i = 0; i < node.size(); i++){
        cout << node[i] << " ";
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    while(1){
        int x, y;
        cin >> x >> y;
        if(x == -1 && y == -1) break;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요