[백준/JAVA] 18243번: Small World Network

📖 문제

18243번: Small World Network

 

 

💡  풀이 방식

• 플로이드-워셜

- 최단 경로 배열을 모두 큰 값으로 초기화한다. (단, 행과 열이 같은 경우는 0으로 설정)

- 입력받은 두 점 간 거리를 1로 설정한다.

- 플로이드-워셜을 통해 모든 정점 간의 최소 거리를 구한다.

- 7단계 이상인 단계가 존재하는 경우, Big World를 출력한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static final int INF = Integer.MAX_VALUE;
    
    static int N, K;
    static int[][] dist;    // 최단 거리 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        // 최단 거리 배열 초기화
        dist = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                if(i == j) continue;
                dist[i][j] = INF;
            }
        }
        
        while(K --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            dist[a][b] = 1;
            dist[b][a] = 1;
        }
        
        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;   // 출발지=경유지 or 경유지=도착지 or 도착지=출발지면 pass
                    
                    if(dist[i][k] != INF && dist[k][j] != INF) {    // 출발지-경유지 길이 있고, 경유지-도착지 길이 있는 경우
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j < i ; j++) {
                if(i == j)  continue;
                
                if(dist[i][j] == INF || dist[i][j] > 6) {
                    System.out.println("Big World!");
                    return;
                }
            }
        }
        
        System.out.println("Small World!");
    }
}
 

 

 

➕ 다른 풀이 방식

플로이드-워셜 부분에서 위처럼 if문 작성할 필요가 없다.

dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

 

---

💦 어려웠던 점

- 최단 거리 갱신할 때 식을 dist[k][j] + 1로 했었는데 그게 아니고, dist[i][k] + dist[j][k] 로 하면 되는 것이었다~

- 플로이드-워셜 3중 for문에서 j 범위를 i까지 해서 73-76%에서 틀렸었다. 다시 N으로 범위 바꿔주니까 정상작동 되었음!

- 문제 보자마자 플로이드-워셜인 걸 떠올렸다. 잊고 있던 플로이드-워셜 복기 성공~~

 

 

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

---

(참고)

 

백준 No.18243 Small World Network - JAVA

 

[백준] S1 18243번 Small World Network (JAVA)