백준 21278번 호석이 두 마리 치킨[골드 4][C++]

1. 개요

 안녕하세요. 이번 문제의 유형은 플로이드-와샬입니다. 플로이드-와샬은 다이나믹 프로그래밍을 이용하는 웰노운 알고리즘입니다. 원리나 구현 난이도가 어렵지 않아서 한 번 공부하면 오래 기억할 수 있습니다. 플로이드-와샬과 별개로 문제를 읽은 다음 플로이드-와샬을 적용할 수 있는지 판단하기 어려울 수도 있는데요. 아래의 내용에 해당이 된다면 고려해 볼 수 있습니다.

1. 정점의 개수가 1,000 이하이다.
2. 모든 정점에서 다른 정점까지의 최단 거리를 구해야 한다.

여기서 1번 조건은 항상 부합하진 않아도됩니다.  플로이드-와샬은 캐시 친화적인 알고리즘이라 1,000을 초과하더라도 TLE 없이 AC를 받는 경우가 있습니다. 하지만 출시자가 플로이드-와샬 알고리즘 사용을 의도했다면 정점의 개수를 크지 않게 설정하므로 유의해야 할 조건이라 명시해 두었습니다. 

2. 문제풀이

2-1. 플로이드-와셜 판단 기준

 문제에서는 N개의 정점 중 2개를 선택해 치킨집을 오픈합니다. 선택된 두 정점은 다른 정점의 접근성의 합이 최소가 되는 곳입니다. 접근성이란 임의의 정점과 선택된 두 정점 중 거리가 더 가까운 정점까지의 왕복 시간입니다. 아직 N개의 정점 중 선택해야 할 곳이 어디인지는 모릅니다. 따라서 모든 정점에서 다른 정점까지의 최단 거리를 구해야 합니다.

 모든 정점에서 다른 정점까지의 최단 거리를 구해야 할 필요가 있는데 정점의 개수는 최대 100개입니다. 따라서 플로이드-와샬을 고려해 볼 수 있습니다.

 

2-2. 접근성의 합이 최소가 되는 두 정점 선택

그래프를 인접행렬로 모델링한 다음 플로이드-와샬을 수행합니다. 인접 행렬은 플로이드-와셜 수행의 결과로 최단 거리 테이블이 되었습니다. loop문으로 두 정점을 선택하여 각 정점에서의 접근성을 계산하여 더해주고 그중 최소가 되는 값을 찾으시면 쉽게 풀이할 수 있습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int INF = 0x3f3f3f3f;

int n, m;
int d[105][105];

int main() {
    fastio(nullptr, false);

    fill(&d[0][0], &d[101][101], INF);

    cin >> n >> m;
    while(m--) {
        int u, v;
        cin >> u >> v;
        d[u][v] = d[v][u] = 1;
    }

    for(int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }

    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    int ansX{}, ansY{}, ansT{INF};
    for(int u = 1; u <= n; u++) {
        for(int v = u + 1; v <= n; v++) {
            int cnt{};
            for(int i = 1; i <= n; i++) {
                cnt += min(d[u][i], d[v][i]) << 1;
            }

            if(cnt < ansT) {
                tie(ansX, ansY, ansT) = {u, v, cnt};
            }
        }
    }
    
    cout << ansX << ' ' << ansY << ' ' << ansT;
}

4. 제출 결과