(C++) - 백준(BOJ) 1058번 : 친구

www.acmicpc.net/problem/1058

1058번: 친구

brute force로 친구 사이의 거리가 2이하인 간선을 세는 floyd warshell 문제였습니다.

 

풀이방법

 1. 친구 i,j사이의 거리를 구합니다. i,j로 가는 거리보다 i -> k -> j로 가는 거리가 더 짧을 때 거리를 갱신하는 방식으로 모든 친구들에 적용합니다.

 

 2. 구한 거리 배열 dist를 모두 순회하며 i의 모든 친구 사이의 거리가 2이하라면 세줍니다.  매번 i가 바뀔 때마다 최대값을 저장합니다.

 

 3. 답을 출력합니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int n, ans;
int friendGraph[51][51];
int dist[51][51];
int main(){
    cin >> n;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            dist[i][j] = INF;

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < s.size(); j++){
            if(s[j] == 'Y') friendGraph[i][j] = 1, dist[i][j] = 1;
            else friendGraph[i][j] = 0;
        }
    }

    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(dist[i][j] > dist[i][k] + dist[k][j]){
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    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++;
        }
        ans = max(ans,cnt);
    }
    
    cout << ans <<'\n';

}