백준 1058번 친구 C++

문제

 

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

---

Algorithm

직접 친구라면 2-친구이다.( 거리 = 1)
혹은 내가 어떠한 대상 A와 2-친구가 되려면, A와 직접 친구인 누군가와 직접 친구여야 한다. (거리 = 2)
위 두 조건 중 하나라도 만족하면 2-친구이다.

즉, 나와 대상의 거리가 2 이하라면 2-친구이다!
이제 BFS를 돌리면 된다.

 

---

 

 

Code

#include <bits/stdc++.h>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

int n;
vector<int> graph[51];
bool visited[51];

void INPUT()
{
    IAMFAST
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        string str; cin >> str;
        for (int j = 0; j < n; j++)
        {
            if (str[j] == 'Y')
            {
                graph[i].emplace_back(j);
                graph[j].emplace_back(i);
            }
        }
    }
}

int BFS(int start)
{
    int cnt = 0;

    queue<int> q;
    memset(visited, false, sizeof visited);
    visited[start] = true;
    for (auto s : graph[start])
        if (!visited[s]) q.emplace(s), cnt++, visited[s] = true;

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (auto next : graph[now])
        {
            if (visited[next]) continue;

            visited[next] = true;
            cnt++;
        }

    }
    return cnt;
}

void solution()
{
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(BFS(i), ans);
    cout << ans;
}

int main()
{
    INPUT();
    solution();
}