백준 1058번 친구 (JAVA)

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

1058번: 친구

 

저는 플루이드-워샬 알고리즘을 활용하여 2-칭구를 찾았습니다.

플루이드-워샬은 n^3방법으로 비효율적일 수 있지만 코드가 간결하고 입력값이 50이라 시간초과가 나지 않을 것이라 판단하여 사용하였습니다.

마지막으로 각 행에 대한 Y를 찾고 이 수가 가장 큰 값을 결과로 출력하였습니다. 

 

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1058 {
    static boolean map[][];
    static int n;
    static int cal(){
        boolean[][] temp = new boolean[n][n];
        for(int k = 0 ; k < n ; k++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j <n ; j++){
                    if(i != j && !map[i][j] && map[i][k] && map[k][j]){
                        temp[i][j] = true;
                    }
                }
            }
        }
        int result = 0;
        for(int i = 0; i < n; i++){
            int sum = 0;
            for(int j = 0; j <n ; j++){
                if(map[i][j] || temp[i][j]){
                    sum++;
                }
            }
            result = Math.max(sum,result);
        }
        return result;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        n = stoi.apply(st.nextToken());
        map = new boolean[n][n];
        for(int i = 0; i < n; i++){
            String command = br.readLine();
            for(int j = 0; j <n ; j++){
                char now = command.charAt(j);
                if('Y' == now){
                    map[i][j] = true;
                }else{
                    map[i][j] = false;
                }
            }
        }
        System.out.println(cal());

    }
}