문제출처: https://www.acmicpc.net/problem/2660
풀이
문제를 읽어보면 친구 관계를 그래프로 표현하여 관계가 어떻게 연결되어있는지를 코딩해야 함을 직감할 수 있습니다.
저는 처음에 문제가 이해가 가지않아서 예제 케이스를 그려보며 규칙을 확인했는데, 결과적으로
모든 노드에서 bfs함수를 돌려서 각 경우의 최대 깊이(depth)를 구한 다음 그 중에서 제일 낮은 깊이를 갖는 경우가 회장 후보가 됨을 알 수 있었습니다.
뎁스는 visited배열을 이용하여 구했고 1,2,3,4,5노드에서 각각 bfs를 돌려보면 뎁스가 각각 3,2,2,3이 나오게 되고, 낮은 점수를 갖는 사람이 회장 후보가 되기 때문에 저 데이터를 이용해 후보점수는 2, 후보인원은 3명임을 알 수 있었습니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int n;
vector<int>map[51];
int score[51];
void bfs(int start);
int main()
{
int a, b;
int cnt = 0;
cin >> n;
while(1){
cin >> a >> b;
if (a == -1 && b == -1)break;
map[a].push_back(b);
map[b].push_back(a);
}
for (int i = 1; i <= n; i++)
bfs(i);
//value 3: 1,5노드
//value 2: 2,3,4노드
int val = score[1];
for (int i = 1; i <= n; i++)
val = (score[i] > val) ? val : score[i];
for (int i = 1; i <= n; i++)
if (val == score[i])cnt++;
cout << val << " " << cnt << endl;
for (int i = 1; i <= n; i++)
if (score[i] == val)cout << i << " ";
}
void bfs(int start)
{
queue<int>q;
int visited[51];
memset(visited, 0, sizeof(visited));
q.push(start);
visited[start] = 1;
while (!q.empty())
{
int num = q.front();
q.pop();
for (int i = 0; i < map[num].size(); i++)
{
int y = map[num][i];
if (!visited[y])
{
q.push(y);
visited[y] = visited[num] + 1;
}
}
}
//all depth from start Node is filled.
int num = 0;
for (int i = 1; i <= n; i++)
num = (visited[i] > num) ? visited[i] : num;
score[start] = num - 1;//start node value=1 -> minus 1
}
|
cs |
결과
