SHARE
TWEET

Untitled

a guest Jul 21st, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <queue>
  2. #include <vector>
  3. #include <string>
  4. #include <cstring>
  5. #include <iostream>
  6.  
  7. using namespace std;
  8.  
  9. #define max(n, m) n > m ? n : m
  10.  
  11. vector<int> mat[51];
  12. int dist[51];
  13.  
  14. int main(void) {
  15.     ios_base::sync_with_stdio(false);
  16.     cin.tie(nullptr);
  17.  
  18.     int n;
  19.     cin >> n;
  20.     for (int i = 1; i <= n; i++) {
  21.         string s; cin >> s;
  22.         for (int j = 0; j < n; j++) {
  23.             if (s[j] == 'Y') {
  24.                 mat[i].push_back(j + 1);
  25.             }
  26.         }
  27.     }
  28.  
  29.     int ans = 0;
  30.     for (int i = 1; i <= n; i++) {
  31.         int tmp = 0;
  32.         memset(dist, -1, sizeof(dist));
  33.         queue<int> q;
  34.         q.push(i);
  35.         dist[i] = 0;
  36.         while (!q.empty()) {
  37.             int x = q.front();
  38.             q.pop();
  39.  
  40.             if (dist[x] == 2) break;  // 거리가 2인 정점이 나왔다는 것은 거리가 1인 것까지 모두
  41.             for (int k = 0; k < mat[x].size(); k++) {
  42.                 int y = mat[x][k];
  43.                 if (dist[y] != -1) continue;
  44.                 dist[y] = dist[x] + 1;
  45.                 tmp += 1;
  46.                 q.push(y);
  47.             }
  48.         }
  49.         ans = max(tmp, ans);
  50.     }
  51.  
  52.     cout << ans << '\n';
  53.     return 0;
  54. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top