[1058번] 친구

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 플로이드 워셜 알고리즘 :: http://www.crocus.co.kr/search/플로이드 워셜?page=2

문제를 이해하면 다음과 같은 의미가 된다.

현재 정점에서 길이가 2 이하인 다른 정점들로 갈 때 총 몇가지인지 구하는데 이중 최대를 구하시오.

결국 n제한이 50이기에 O(50^3) = O(125,000)에 해결이 가능하다는 것은 플로이드 워셜로 가능하다는 의미가 된다.

소스 코드 : 

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

#include <iostream> #include <cstdio> #include <memory.h> #include <algorithm>   #define INF 987564231   using namespace std;   int adj[52][52];   int main() {     int n;     scanf("%d", &n);            for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)             i == j ? adj[i][j] = 0 : adj[i][j] = INF;       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)         {             char ch;             scanf(" %c", &ch);               if (ch == 'N')                 continue;               adj[i][j] = adj[j][i] = 1;         }          for (int k = 0; k < n; k++)         for(int x = 0; x < n; x ++)             for (int y = 0; y < n; y++)                 if (adj[x][y] > adj[x][k] + adj[k][y])                     adj[x][y] = adj[x][k] + adj[k][y];                  int ans = 0;     for (int i = 0; i < n; i++)     {         int cnt = 0;         for (int j = 0; j < n; j++)             if (adj[i][j] <= 2)                 cnt++;              ans = max(ans, cnt);     }       printf("%d", ans - 1);          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus