넘치게 채우기

[BOJ] 1058 - 친구 본문

PS/BOJ

[BOJ] 1058 - 친구

riveroverflow 2024. 12. 1. 11:21
728x90
반응형

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
 
 
728x90
반응형

'PS > BOJ' 카테고리의 다른 글

[BOJ] 11444 - 피보나치 수 6  (0) 2024.12.02
[BOJ] 1105 - 팔  (0) 2024.12.02
[BOJ] 1024 - 수열의 합  (0) 2024.11.30
[BOJ] 1918 - 후위 표기식  (0) 2024.11.28
[BOJ] 1167 - 트리의 지름  (0) 2024.11.27