반응형

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

 

2660번: 회장뽑기

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/24

 

[ 알고리즘 ] 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)

오늘 설명할 알고리즘은 플로이드 와샬 알고리즘(Floyd Warshall Algorithm)입니다. 이 알고리즘은 dijkstra와 비슷하게 각 정점까지 가는 최단 거리를 알아낼 수 있습니다. 플로이드 와샬 알고리즘이 dijk

rudalsd.tistory.com

 

1. arr[ n ][ n ] 배열을 만들어서 서로 친구관계라면 1로 초기화합니다.

 

2. 플로이드 와샬 알고리즘을 이용하여 각 회원끼리 몇 단계를 거쳐야 친구가 되는지 저장합니다.

 

3. 1번 회원부터 N번 회원까지 각 회원들의 가장 먼 친구관계를 저장합니다.

 

4. 그 중 가장 가까운 친구관계가 몇 단계인지 min에 저장하고, 그 후보들을 ans에 push 합니다.

 

5. min과 ans.size를 출력하고, ans의 값들을 하나씩 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int N;
int arr[51][51];
int point[51];
vector<int> ans;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i != j) {
                arr[i][j] = 9999;
            }
        }
    }
 
    while (1) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (a == -1 && b == -1) break;
 
        arr[a][b] = 1;
        arr[b][a] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                if (arr[j][k] > arr[j][i] + arr[i][k]) {
                    arr[j][k] = arr[j][i] + arr[i][k];
                }
            }
        }
    }
 
    int min = 9999;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            point[i] = max(point[i], arr[i][j]);
        }
 
        if (min > point[i]) {
            min = point[i];
            ans.clear();
            ans.push_back(i);
        }
        else if (min == point[i]) {
            ans.push_back(i);
        }
    }
 
    printf("%d %d\n", min, (int)ans.size());
 
    for (int next : ans) {
        printf("%d ", next);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 17396번 - 백도어 (C++)  (0) 2023.03.02
[ 백준 ] 3066번 - 브리징 시그널 (C++)  (0) 2023.03.01
[ 백준 ] 2617번 - 구슬 찾기 (C++)  (0) 2023.02.27
[ 백준 ] 18235번 - 지금 만나러 갑니다 (C++)  (0) 2023.02.26
[ 백준 ] 18405번 - 경쟁적 전염 (C++)  (0) 2023.02.25

+ Recent posts

티스토리툴바