[BOJ알고리즘, C++]#2660_회장 뽑기, 그래프, BFS

 

#1. 문제

 

2660번: 회장뽑기

 

---

 

#2. 풀이

 

1. 그래프

 

[자료구조]#6_그래프

 

그래프 자료구조는 노드와 간선의 집합으로 이루어진 비 선형 자료구조입니다. 그래프 자료구조의 노드 간 연결 관계는 간선으로 나타내며, 간선의 방향성, 연결 강도에 따라서 다양한 형태의 그래프를 나타낼 수 있습니다.

 

2. BFS, 너비 우선 탐색

 

[자료구조]#6_그래프

 

BFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 현재 정점과 인접한 정점들을 우선적으로 탐색하는 방법입니다. 일반적으로, BFS는 큐 자료구조를 활용하여 구현 가능합니다. 특히, 각 간선의 가중치가 일정할 경우, 다음 후보 경로에 대한 우선순위가 존재하지 않기 때문에, BFS를 활용하여 특정 경로의 최단 거리 값을 구하는 데 사용되기도 합니다.

 

3. 각 정점을 시작으로 BFS를 수행하고, 최대 점수를 업데이트하자!

 

1. 각 정점을 시작점으로 하는 BFS를 수행하며, 그래프의 모든 정점에 대하여 최단 거리 값을 업데이트해 줍니다. 쉽게 말해, 현재 정점과 가장 멀리에 있는 경로 길이를 찾아 해당 정점의 "점수"로 기억하는 것입니다.

 

---

 

#3. 코드

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int N;
vector<vector<int>> graph;
vector<int> scores;
vector<bool> visited;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    graph.resize(N + 1);
    scores.resize(N + 1, 0);
    visited.resize(N + 1, false);

    while (true)
    {
        int u, v;
        cin >> u >> v;
        if (u == -1 && v == -1)
            break;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for (int i = 1; i <= N; ++i)
    {
        queue<pair<int, int>> q;
        q.push({i, 0});
        visited.assign(N + 1, false);

        while (!q.empty())
        {
            int cur = q.front().first;
            int dist = q.front().second;
            q.pop();

            if (visited[cur])
                continue;
            visited[cur] = true;

            scores[i] = max(scores[i], dist);

            for (int next : graph[cur])
            {
                if (!visited[next])
                {
                    q.push({next, dist + 1});
                }
            }
        }
    }

    int minMaxScore = INF;
    for (int i = 1; i <= N; ++i)
    {
        minMaxScore = min(minMaxScore, scores[i]);
    }

    vector<int> candidates;
    for (int i = 1; i <= N; ++i)
    {
        if (scores[i] == minMaxScore)
        {
            candidates.push_back(i);
        }
    }

    cout << minMaxScore << ' ' << candidates.size() << '\n';
    for (int candidate : candidates)
    {
        cout << candidate << ' ';
    }
    cout << '\n';

    return 0;
}

 

---