[백준] S2 1058번 친구 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1058번: 친구

[문제] 

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

[입력]

첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

[출력]

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

 

 

---

[풀이]

1. 값을 입력받으면서 N의 경우 max값을, Y의 경우 1의 값을 주었다.

2. 플루이드 와샬을 사용해서 친구의 연결을 구해준다.

3. 그 후, 각 사람에게 연결된 친구를 구해서 가장 많은 2-친구의 수를 구해준다.

[접근]

1. n의 크기가 50까지이므로 플루이드 와샬을 사용해서 문제를 풀 수 있을 것이라고 생각하였다.

2. 플루이드 와샬을 사용해 연결된 친구들을 모두 구해주고 결과를 구하는 식으로 문제를 풀었다.

[코드]

package BOJ_silver;

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

public class Main_S2_1058 {
	static int n;
	static int arr[][];
	static int max = Integer.MAX_VALUE >> 2; // 최대값을 주기
	static int ans;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];
        
        // 값 입력받기
        for(int i = 1; i <= n; i++) {
            String str = br.readLine();
            
            for(int j = 1; j <= n; j++) {
                char ch = str.charAt(j - 1);
                
                if(ch == 'Y')
                    arr[i][j] = 1;
                else if(i != j)
                    arr[i][j] = max;
            }
        }
        
        // 플루이드 와샬
        for(int k = 1; k <= n; k++) { // 경유지
            for(int i = 1; i <= n; i++) { // 출발지
                for(int j = 1; j <= n; j++) { // 도착지
                    if(i == j || j == k || i == k)
                        continue;
                    else if(arr[i][j] > arr[i][k] + arr[k][j])
                        arr[i][j] = arr[i][k] + arr[k][j];
                }
            }
        }
        
        for(int i = 1; i <= n; i++) {
            int tmp = 0;
            
            for(int j = 1; j <= n; j++) {
                if(i == j) // 자기 자신은 건너뛰기
                    continue;
                // 2-친구인 경우
                else if(arr[i][j] <= 2)
                    tmp++;
            }
            // 더 큰 값으로 갱신
            ans = Math.max(ans, tmp);
        }
        
        // 결과 출력
        System.out.println(ans);
    }
}