[BOJ] 1058 - 친구

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

BOJ - 친구

문제 유형: bfs

문제 난이도: Silver II

시간 제한: 2초

메모리 제한: 128MB

 

문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

 

입력

첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

 

출력

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

 

풀이

친구와 친구의 친구까지가 2-친구이다.

즉, 입력 정보를 인접행렬이라고 가정하고, bfs를 두 사이클 돌려주면서 2-친구를 구할 수 있다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n;
  vector<string> adj(n);
  for (int i = 0; i < n; ++i) {
    cin >> adj[i];
  }

  int ans = 0;

  for (int i = 0; i < n; ++i) {
    queue<int> q;
    vector<bool> visited(n, false);
    q.push(i);
    visited[i] = true;
    int t = 2;
    int cnt = 0;
    while (!q.empty() && t--) {
      int qsize = q.size();
      for (int j = 0; j < qsize; ++j) {
        int curr = q.front();
        q.pop();

        for (int k = 0; k < n; ++k) {
          if (!visited[k] && adj[curr][k] == 'Y') {
            cnt++;
            visited[k] = true;
            q.push(k);
          }
        }
      }
    }
    ans = max(ans, cnt);
  }

  cout << ans << "\n";

  return 0;
}

입력

[명사] entry, [동사] enter, input