[BOJ/C++] 21278 호석이 두 마리 치킨

시간 복잡도

• N이 최대 100이므로 $O(N^3)$인 플로이드 워셜 알고리즘을 이용하여 해결할 수 있습니다.

문제 접근법

• 플로이드-워셜 알고리즘을 이용하여 모든 건물간의 최단 경로를 구합니다.
• 이중반복문을 이용해 건물을 오름차순으로 순회합니다. (1, 2), (2, 3) ...
• 두 건물중 더 가까운 건물에 대한 거리를 모든 건물에 대해 더합니다.
• 더한 결과가 치킨집 2개를 기준으로 빌딩에서 가까운 모든 치킨집에 대한 거리의 합입니다.
• 거리의 합이 작다면 두 건물의 번호와 거리의 합을 업데이트합니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;


static int Dist[101][101];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    int V, E;
    cin >> V >> E;

    // 최단 거리 배열 초기화
    for(int i=0; i<101; i++)
    {
	    for(int j=0; j<101; j++)
	    {
            if (i == j)
                Dist[i][j] = 0;
            else
                Dist[i][j] = 1000001;
	    }
    }
    
    for(int i=0; i<E; i++)
    {
        int s, e;
        cin >> s >> e;

        Dist[s][e] = 1;
        Dist[e][s] = 1;
    }

    // 플로이드-워셜
    for(int k=1; k<=V; k++)
    {
	    for(int i=1; i<=V; i++)
	    {
		    for(int j=1; j<=V; j++)
		    {
                Dist[i][j] = min(Dist[i][j], Dist[i][k] + Dist[k][j]);
		    }
	    }
    }


    int building1, building2, distance = INT_MAX;
    for(int i=1; i<=V; i++)
    {
	    for(int j=i+1; j<=V; j++)
	    {
            int sum = 0;
            for(int k=1; k<=V; k++)
            {
                sum += min(Dist[i][k], Dist[j][k]);
            }

            if (distance > sum)
            {
                building1 = i;
                building2 = j;
                distance = sum;
            }
	    }
    }


    cout << building1 << ' ' << building2 << ' ' << distance*2;

    return 0;
}