백준 No.1058 친구- JAVA

문제

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

 

풀이 

문제를 많이 읽어봤지만 이해를 못해 결국 답을 봤다. 플로이드 와샬을 통해 각 최단 경로를 구하고 2나 1을 찾아 최댓값을 구한다.

플로이드 와샬에서는 최단경로를 구하기 위해

for(int i = 1; i <= N;i++){
    for(int j = 1;j<=N;j++){
        for(int k = 1;k<=N;k++){
            if(j == k) continue;
            cost[j][k] = Math.min(cost[j][k],cost[j][i]+cost[i][k]);//J 시작 K 도착
        }
    }
}

이론 코드를 실행하는데 해당 코드를 설명하면

모든 노드들 간의 최단 경로를 찾는 과정을 수행한다. 

1. i번째 노드를 거쳐가는 경우를 고려하여 모든 노드들의 최단 경로를 갱신한다. 

2. for문의 첫 번쨰 루프에서 i는 거쳐가는 노드의 인덱스를 나타낸다. 즉 1부터 N까지의 모든 노드들을 한 번씩 거쳐가는 경우를 검사한다. 

3. for문의 두 번째와 세 번쨰 루프에서 j와 k는 출발 노드와 도착 노드의 인덱스를 나타낸다. 따라서 j부터 k까지의 최단 경로를 갱신하는 것이 목표이다. 

4. cost[j][k]는 j 에서 k로 가는 경로의 현재 최단 거리를 나타내며 ,cost[j][i]+cost[i][k]는 j에서 i를 거쳐 k 로 가는 경로의 거리를 나타낸다.

5. Math.min 함수를 사용하여 현재의 최단 거리와 거쳐가는 경로를 비교하여 더 작은 값으로 갱신한다. 이를 통해 더 짧은 경로를 찾아내고 최단 경로를 찾아가는 과정을 반복한다.

6. 이러한 과정을 모든 노드들에 대해 수행하면 최종적으로 모든 노드들 간의 최단 경로가 계산된다.

 

 

 

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

public class Main {

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


    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 i = 1; i <= N;i++){
            for(int j = 1;j<=N;j++){
                for(int k = 1;k<=N;k++){
                    if(j == k) continue;
                    cost[j][k] = Math.min(cost[j][k],cost[j][i]+cost[i][k]);
                }
            }
        }


        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);
    }
}

 

풀이참고

https://dev-gorany.tistory.com/163

[백준] 1058번 : 친구