Game Develop

[Algorithm]Baekjoon 2660번 : 회장 뽑기 본문

Algorithm/Baekjoon

[Algorithm]Baekjoon 2660번 : 회장 뽑기

MaxLevel 2023. 12. 24. 03:54

https://www.acmicpc.net/problem/2660

 

2660번: 회장뽑기

입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터

www.acmicpc.net

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
struct Node
{
    int node;
    int maxScore;
};
 
bool cmp(const Node& a, const Node& b)
{
    if (a.maxScore == b.maxScore)
    {
        return a.node < b.node;
    }
    
    return a.maxScore < b.maxScore;
}
 
int n, a, b;
int adjMatrix[51][51];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    memset(adjMatrix, 0x3f, sizeof(adjMatrix));
 
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
    {
        adjMatrix[i][i] = 0;
    }
 
    while (1)
    {
        cin >> a >> b;
        if (a == -1) break;
 
        adjMatrix[a][b] = 1;
        adjMatrix[b][a] = 1;
    }
 
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (adjMatrix[i][k] + adjMatrix[k][j] < adjMatrix[i][j])
                {
                    adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                }
            }
        }
    }
 
    vector<Node> answers;
 
    for (int i = 1; i <= n; ++i)
    {
        int maxScore = 0;
        
        for (int j = 1; j <= n; ++j)
        {
            maxScore = max(maxScore, adjMatrix[i][j]);
        }
 
        answers.push_back({ i,maxScore });
    }
 
    sort(answers.begin(), answers.end(), cmp);
 
    int answerCount = 1;
 
    
    for (int i = 1; i < answers.size(); ++i)
    {
        if (answers[i].maxScore != answers[0].maxScore) break;
        ++answerCount;
    }
 
    cout << answers[0].maxScore << ' ' << answerCount << endl;
    for (int i = 0; i < answerCount; ++i)
    {
        cout << answers[i].node << ' ';
    }
}
 cs

 

각 노드끼리의 최단거리를 구해야하는 문제이다.

인풋값도 작기때문에 플로이드와샬을 사용하면 쉽게 해결할 수 있다.

'Algorithm > Baekjoon' 카테고리의 다른 글

[Algorithm] Baekjoon 1021번 : 회전하는 큐  (0) 2023.12.27
[Algorithm] Baekjoon 17142번 : 연구소 3  (1) 2023.12.25
[Algorithm]Baekjoon 11060번 : 점프 점프  (0) 2023.12.15
[Algorithm]Baekjoon 1495번 : 기타리스트  (0) 2023.12.14
[Algorithm]Baekjoon 1976번 : 여행 가자  (0) 2023.12.13
'Algorithm/Baekjoon' Related Articles more