[C++] 2660 회장뽑기 | 그래프(Graph)

1. 간단한 그래프 탐색 문제이다. 

edge의 방향성에 대한 설명이 없으니 양방향 그래프다.

 

그래프 node와 edge 입력은 요새

벡터 리스트를 만들어 각 벡터요소가 하나의 node이고

edge로 연결된 node들을 벡터에 추가하는 방식을 자주 활용한다.

 

2. 회원 i를 root로 생각했을 때, 그래프의 depth가 '점수'가 된다.

문제 설명은 한번 읽으면 난해하게 느껴지지만, 예시를 한번 그려보면

쉽게 상황 파악이 된다.

 

3. 코드

#include <iostream>

#include <vector>

#include <queue>

#include <set>

using namespace std;

int N;

int BFS(vector<int> *fri, int root) {

 

bool *visited = new bool[N]();

visited[root] = true;

int depthFromRoot = 0;

int depth[N];

depth[root] = 0;

queue<int> q;

q.push(root);

while(!q.empty()) {

int cur = q.front();

q.pop();

for (int i = 0; i < fri[cur].size(); i++) {

int curChld = fri[cur][i];

if (!visited[curChld]) {

visited[curChld] = true;

q.push(curChld);

depth[curChld] = depth[cur] + 1;

if (depthFromRoot < depth[curChld])

depthFromRoot = depth[curChld];

}

}

}

return depthFromRoot;

}

int main() {

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

/*입력*/

cin >> N;

vector<int> *fri = new vector<int>[N];

while (1) {

int a, b;

cin >> a >> b;

if (a == -1 && b == -1)

break;

fri[a - 1].push_back(b - 1);

fri[b - 1].push_back(a - 1);

}

/*계산*/

int *score = new int[N]();

int minScore = 50;

for (int i = 0; i < N; i++) {

score[i] = BFS(fri, i);

 

if (minScore > score[i])

minScore = score[i];

}

/*출력*/

set<int> candi;

for (int i = 0; i < N; i++) {

if (score[i] == minScore) {

candi.insert(i + 1);

}

}

cout << minScore << " " << candi.size() << "\n";

set<int>::iterator iter;

for (iter = candi.begin(); iter != candi.end(); iter++)

cout << *iter << " ";

cout << "\n";

return 0;

}