[백준] 1058번 : 친구

1058번: 친구

---

[플로이드 - 와샬, Floyd - Warshall]

A, B, C, D, E가 있다고 하자. A와 B가 친구이고, B와 C가 친구일 때 A와 C는 친구이다. 그럼 C와 D가 친구일 때 A와 D는 친구일까? 아니다. 2-친구이므로 나의 친구의 친구까지만 친구로 인정된다. 따라서 D는 A의 3-친구이다. 이 문제에서는 2-친구만을 답으로 원하므로 플로이드 와샬을 수행하여 각 친구들이 n-친구인지 구하고 2 이하인 친구들의 개수를 구하도록 한다. (0일 때는 친구가 아니므로 pass, 1와 2일 때만 카운트를 증가한다.)

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static final int INF = 100000000;
    static int[][] cost = new int[51][51];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=n; j++) {
                if(i == j) continue;

                cost[i][j] = str[j-1] == 'Y'? 1 : INF;
            }
        }

        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++) {
                    if (i == j) continue;

                    cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                }

        int max = 0;
        for(int i=1; i<=n; i++) {
            int cnt = 0;

            for (int j = 1; j <= n; j++)
                if (cost[i][j] == 2 || cost[i][j] == 1) cnt++;

            max = Math.max(max, cnt);
        }

        System.out.println(max);
    }
}