백준 2660 : 회장뽑기

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

가장 기본적인 플로이드-와샬 알고리즘 문제이다.

다익스트라는 한 점을 기준으로 해서 다른 점들과의 최소비용거리를 계산하지만

플로이드-와샬 같은경우 모든 점과 점사이의 경로를 구한다.

모든 점과 점사이의 최소비용거리 데이터는 2차원 배열에 저장이 되며 시간복잡도는 n^3 이다.

플로이드-와샬 알고리즘의 경우 동적계획법(DP)의 형태를 가진다.

우선 모든 2차원 배열에 저장된 경로를 INF으로 선언하고(자기자신으로 가는경우 i==j 는 0)

각 i -> j 로 갈 때 가중치를 저장해준다. ( i -> j 로 가는 경로가 없을때 INF 선언)

현재 정점에서 목적지로 갈때 직접 가는 것보다 다른 점을 거쳐가는 것이 더 빠른 경우를 찾는것

이 핵심이다.

간단하게 for문 3번 돌려주면 된다.

for(int k = 1; k <= n; k++){

for(int i = 1; i <= n; i++){

for(int j = 1; j <= n; j++){

if( matrix[i][j] > matrix[i][k] + matrix[k][j] ){

// i-j 직접가는 것보다 i-k, k-i 거쳐서 가는 것이 더 이득일때 최소비용을 갱신

matrix[i][j] = matrix[i][k] + matrix[k][j];

}

}

}

}

만약 matrix[i][j] 에서 INF값이 남아 있다면 그 해당 j 점은 아무 점과도 연결이 안되어있다는 뜻이다.

이 문제에서는 사실 최소비용은 필요없다 i 에 속한 j 를 모두 탐색하면서 INF (연결안됨) 만 제외하고 최대값을 찾으면 된다.

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

#include <iostream> #include <vector> #include <algorithm> #define MAX 51 #define INF 1000000000 using namespace std; int n; int matrix[MAX][MAX]; int score[MAX]; void Floyd(){ for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(matrix[i][j] > matrix[i][k] + matrix[k][j]){ matrix[i][j] = matrix[i][k] + matrix[k][j]; } } } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ matrix[i][j] = (i==j) ? 0:INF; } } while(true){ int a, b; cin >> a >> b; if(a == -1) break; matrix[a][b] = 1; matrix[b][a] = 1; } Floyd(); int hoobo = -1; for(int i = 1; i <= n; i++){ int max = 0; for(int j = 1; j <= n; j++){ if(matrix[i][j] > max){ max = matrix[i][j]; } } score[i] = max; if(hoobo > max || hoobo == -1){ hoobo = max; } } int count = 0; for(int i = 1; i <= n; i++){ if(score[i] == hoobo){ count++; } } cout << hoobo << " " << count << '\n'; for(int i = 1; i <= n; i++){ if(score[i] == hoobo){ cout << i << " "; } } cout << '\n'; return 0; }