[1058] 친구

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

(친구)와 (친구의 친구)의 최대치를 출력하는 문제입니다.

간단하게 생각했고 bfs를 이용하여 너비 2까지 도달하면 탈출하여

방문했던 곳을 전부 체크하면 해결할 수 있는 문제입니다.

어려운 것은 없었습니다.

풀 코드입니다.

#include <iostream>
#include <string.h>
#include <queue>
 
using namespace std;
 
#define ll long long
#define MOD (ll)1e15
#define MAX_SIZE 500000
//ios::sync_with_stdio(false); cin.tie(0);
 
char map[55][55];
bool visit[55];
int n;
 
int bfs(int vertex) {
    memset(visit, 0, sizeof(visit));
 
    queue<pair<int, int> > q;
    
    q.push(make_pair(vertex, 0));
    visit[vertex] = 1;
 
    while (!q.empty()) {
        int now = q.front().first;
        int breath = q.front().second;
        q.pop();
 
        if (breath == 2) break; //친구의 친구가 되면 탈출
 
        for (int i = 0; i < n; i++) {
            if (map[now][i] == 'Y' && !visit[i]) {
                visit[i] = 1;
                q.push(make_pair(i, breath + 1));
            }
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) ret += visit[i];
 
    return ret - 1; // 자기 자신은 제외
}
 
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
 
    //인풋
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> map[i][j];
        }
    }
 
    int ret = 0;
    for (int i = 0; i < n; i++) ret = max(ret, bfs(i));
 
    cout << ret;
 
    return 0;
}