[백준 1058번] 친구 (C++)

문제링크 : https://www.acmicpc.net/problem/1058

#include <bits/stdc++.h>
using namespace std;

int dist[51][51];

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, result = 0;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            dist[i][j] = INT_MAX;
        }
    }

    for(int i=0; i<n; i++)
    {
        string s;
        cin>> s;
        for(int j=0; j<s.size(); j++)
        {
            if(s[j]=='Y')
            {
                dist[i][j] = 1; //친구 간 거리는 1
            }
        }
    }

    for(int j=0; j<n; j++) // 중간 
    {
        for(int i=0; i<n; i++) // 시작 
        {
            for(int k=0; k<n; k++) // 도착 
            {
                if(dist[i][j] == INT_MAX || dist[j][k] == INT_MAX) continue;
                dist[i][k] = min(dist[i][k], dist[i][j] + dist[j][k]); //거리 갱신신
            }
        }
    }

    //가장 2-친구의 수가 많은 사람 찾기
    for(int i=0; i<n; i++)
    {
        int cnt = 0;
        for(int j=0; j<n; j++)
        {
            if(i==j) continue; //자기 자신 스킵
            if(dist[i][j] <=2) cnt++;
        }
        result = max(result, cnt);
    }
    
    cout << result << '\n';

    return 0;
}

 

플로이드 - 워셜 알고리즘을 통해 풀 수 있는 문제이다.

먼저 배열을 최대값으로 지정하고, 이후에 'Y' 값을 기준으로 해당 거리 ij에 대해서 초기 거리 1을 설정해준다.

 

이제 플로이드 워셜 알고리즘을 통해서 가능한 케이스에 대해 거리를 갱신해준다.

거리를 갱신했으면 이제 가장 2-친구의 수가 많은 사람을 찾을 차례이다.

 

브루트포스를 통하여 자기 자신의 경우에는 스킵하고, ij의 거리가 2이하인 경우에 대해 카운팅하고 카운팅한 값 중 가장 큰 값을 출력해준다.