[백준] 1058번 : 친구

문제

www.acmicpc.net/problem/1058

1058번: 친구

문제해결방법

이 문제는 사람을 정점으로 두고 간선의 길이를 1로 가정하고 풀었다.

한 사람에서 다른 사람들까지의 거리를 모두 구해서 2이하인 사람들의 수를 구하는 문제였다.

모든 정점에서 다른 모든 정점까지를 구해야 하기 때문에 플로이스 와샬 알고리즘을 사용해서 풀었다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main1058_친구 {
 
    public static int N, MAX_VALUE = 987654321;
    public static int[][] friends;    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        friends = new int[N][N];
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<N; j++) {
                if(s.charAt(j)=='N') friends[i][j] = MAX_VALUE; 
                else friends[i][j] = 1;
                if(i==j) friends[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(friends[i][j]>friends[i][k]+friends[k][j])
                        friends[i][j]=friends[i][k]+friends[k][j];
                }
            }
        }
        int max = 0;
        for(int i=0; i<N; i++) {
            int count = 0;
            for(int j=0; j<N; j++) {
                if(i==j) continue;
                if(friends[i][j]<=2) count++;
            }
            if(max<count) max = count;
        }
        System.out.println(max);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.