[백준/JAVA] 1058번: 친구

📖 문제

1058번: 친구

 

 

 

💡  풀이 방식

• 플로이드-워셜 (최단경로)

⇨ 시간 복잡도 : O(N^3)

 

필요 자료구조
- 각 사람 간 거리 저장할 2차원 int형 배열
- 2차원 배열에 저장할 상수 변수 INF

 

. 값을 입력받으면서 Y면 1을, N이면 INF (=9999) 값을 저장한다.

. 플로이드-워셜 통해 친구 연결을 구한다.

  - 경로를 확인할 세 사람 中 둘 이상이 같은 경우 (출발지=경유지 or 경유지 = 도착지 or 도착지 = 출발지 인 경우), pass한다.

  - 셋 다 다른 값일 경우, 출발지→경유지까지의 거리 A와 경유지 → 도착지까지의 거리 B가 출발지→도착지까지 한 방에 가는 거리 C보다 작다면, 출발지→도착지까지 가는 거리 C를 A+B의 값으로 갱신한다.

 

. 2차원 배열을 돌면서 매 사람마다 본인→본인으로 가는 경우는 건너뛰고, 다른 사람과 2-친구인 경우 (= 2차원 배열의 값이 2 이하인 경우)의 수를 구하고, 이를 최댓값과 비교해 갱신한다.

 

 

 

💥 유의사항

본인→본인의 경우 제외하기

2-친구 관계 =한 다리 건너 아는 사람까지 친구라는 말

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int INF = 9999;
    
    static int N;
    static int[][] dist;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        dist = new int[N][N];
        
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < N ; j++) {
                if(i == j) {    // 행과 열이 같으면 N
                    dist[i][j] = INF;
                    continue;
                }
                
                char ch = str.charAt(j);
                
                if(ch == 'Y')
                    dist[i][j] = 1;
                else
                    dist[i][j] = INF;
            }
        }
        
        // 플로이드-워셜 통해 친구 연결 구하기
        for(int k = 0 ; k < N ; k++) {  // 경유지
            for(int i = 0 ; i < N ; i++) {  // 출발지
                for(int j = 0 ; j < N ; j++) {  // 도착지
                    if(i == j || j == k || i == k)  continue;
                    
                    if(dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }            
        }
        
        int max = 0;
        for(int i = 0 ; i < N ; i++) {
            int cnt = 0;
            
            for(int j = 0 ; j < N ; j++) {
                if(i == j)  continue;   // 본인은 건너뛰기
                
                if(dist[i][j] <= 2) {   // 2-친구인 경우
                    cnt++;
                }
            }
            
            max = Math.max(max, cnt);   // 더 큰 값으로 갱신
        }
        
        System.out.println(max);
    }
}
 

 

 

➕ 다른 풀이 방식

- 그냥 이렇게 구현만 하면 된다고? 다소 충격적이었다..

[자바] 백준 10864 - 친구 (java)

---

💦 어려웠던 점

플로이드-워셜 알고리즘을 복습해야겠다,,

 

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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