문제 이해

건물의 개수가 N개 존재하고 건물 사이 도로는 M개 존재한다.

건물 중 2개에 치킨집을 지으려 한다.
이 때 모든 건물에서 2개 치킨집 중 가까운 치킨집과의 거리 합을 구하는데, 이 거리 합을 최소로 만드는 경우를 찾아 어떤 건물에 치킨집을 지어야하며, 그 때 걸리는 왕복 시간의 합을 구하는 문제이다.

---

문제 풀이

먼저 치킨 집을 지을 수 있는 경우의 수는 Brute-Force로밖에 구할 수 없다고 판단하였다.
(1,2)에 지을 경우, (1,3)에 지을 경우...를 모두 고려하여 계산하고, 이 중 최소값을 도출해낼 때 치킨집 위치를 반환하는 로직을 구했다.

이것보다 더 큰 문제는 어떻게 건물 사이의 거리를 최소로 계산할 수 있는가였다.

물론 다익스트라 알고리즘을 통해서도 해결할 수 있었겠지만, 건물의 개수 N이 100 이하라는 점을 고려했을 때 플로이드-워셜 방법으로 풀어도 시간 초과가 발생하지 않을 것 같았다.

다익스트라 알고리즘을 통해 풀기 위해서는 모든 노드를 시작점으로 하여 총 N번의 다익스트라 알고리즘을 실행시켜야하고, 이런 과정을 거치느니 맘 편하게 플로이드-워셜을 활용하기로 했다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M;
	static int[][] arr;
	static int max;
	
	static void floid() {
    // 플로이드 워셜 알고리즘
		for(int k =0;k<N;k++) {
			for(int i =0;i<N;i++) {
				for(int j =0;j<N;j++) {
					if(i==j) continue;
                    // i = j일 경우 i -> i로 가는 최소 경로이므로
                    // 원래 저장되어 있던 0값이 그대로 적용되어야 한다.
					
					if(arr[i][k]!=max && arr[k][j]!=max) {
                    // 플로이드 워셜의 핵심 로직
						arr[i][j] = Math.min(arr[i][j], 
                        				     arr[i][k]+arr[k][j]);
					}
				}
			}
		}
	}
	
	static void brute_force(){
		int ans = Integer.MAX_VALUE;
		int left = 0;
		int right = 0;
        
		for(int i =0;i<N-1;i++) {
			for(int j = i+1;j<N;j++) {
            // (i, j)에 치킨집을 지었을 경우 최소 경로
				int sum = 0;
				for(int k=0;k<N;k++) {
					sum+=Math.min(arr[i][k], arr[j][k]);
				}
				
				if(ans > sum) {
                // 현재 (i,j)에 치킨집을 지었을 때 최소 거리의 합이 됨
					ans = sum;
					left=  i;
					right = j;
				}
			}
		}
		
		System.out.println((left+1)+" "+(right+1)+" "+(ans*2));
        // "왕복 거리"를 구하는 것이므로 ans*2를 출력
	}
	
	public static void main(String[] args) {
		int max = 5000;
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		arr = new int[N][N]; 
		for(int i =0;i<N;i++) {
			Arrays.fill(arr[i], max);
			arr[i][i] = 0;
		}
		
		for(int i =0;i<M;i++) {
			int s = sc.nextInt() - 1;
			int e = sc.nextInt() - 1;
			arr[s][e] = 1;
			arr[e][s] = 1;
		}
		
		floid();
		
		brute_force();
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과