[백준 21278번] 호석이 두 마리 치킨 (C++)

문제링크 : https://www.acmicpc.net/problem/21278

21278번: 호석이 두 마리 치킨

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
int dp[101][101];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            if(i==j) continue; //자기자신 제외
            dp[i][j] = MAX;
        }
    }

    for(int i=0; i<M; i++)
    {
        int x, y;
        cin >> x >> y;
        dp[x][y]=1; //양방향, 걸리는 시간 1
        dp[y][x]=1;
    }

    for (int k=1; k<=N; k++) //플로이드 워셜
    {
		for (int i=1; i<=N; i++) 
        {
			for (int j=1; j<=N; j++)
            {
				if (dp[i][j] > dp[i][k] + dp[k][j]) 
                {
					dp[i][j] = dp[i][k] + dp[k][j];
				}
			}
		}
	}

    tuple<int, int, int> result = make_tuple(MAX, MAX, MAX); //건물번호 1, 2, 시간합

    for (int i = 1; i <= N; i++) //치킨집 1
    {
		for (int j = i + 1; j <= N; j++) //치킨집 2
        {
			int sum = 0;
			for (int k = 1; k <= N; k++) //건물
            {
				sum += min(dp[k][i] * 2, dp[k][j] * 2); //짧은 왕복거리 총합 저장
			}
			if (get<2>(result) > sum) //최소 거리 및 거리에 대한 위치 갱신
            {
				result = make_tuple(i, j, sum);
			}
		}
	}

    cout << get<0>(result) << " " << get<1>(result) << " " << get<2>(result);

    return 0;
}

 

플로이드 워셜을 이용한 문제이다.

먼저 입력받은 값에 대해 걸리는 시간이 1이고, 양방향 이동이 가능하기에 각 방향에 대 1로 초기화를 해준다.

 

이후 플로이드 워셜 알고리즘을 이용해 최단거리를 구해준다.

N의 크기가 100밖에 되지않기 때문에 3중 for문을 사용한 플로이드 워셜 알고리즘의 사용이 가능하다.

 

그 다음에 바로 튜플을 선언해주는데, 이는 건물번호 2개와 해당 건물번호에 대한 왕복시간합을 저장하기 위함이다.

이후 다시 3중 반복문을 사용하는데 i와 j은 치킨집 1, 2 k는 현재 건물이다.

현재 지정한 치킨집 2개를 기준으로 건물을 옮겨가며 걸리는 시간이 더 짧은 건물을 선택한다.

이때 시간은 왕복시간을 재야하므로 *2를 하여 합에 더해준다.

이렇게 더한 합이 현재 고른 치킨집을 기준으로 한 모든 도시에서의 왕복 시간의 합이 된다.

 

이제 이 합이 최소가 되어야 하므로 tuple에서 선언했던 맨 마지막 값을 이용하여 최소값을 갱신해준다.

치킨집을 옮겨가며 모든 경우에 대해 위의 탐색을 반복해주고, 합이 제일 작을 때의 치킨집 위치와 합을 tuple에 넣어주고 이 tuple 값을 출력해주면 된다.