백준 21278 호석이 두 마리 치킨

https://www.acmicpc.net/problem/21278

#include <iostream>
#include <vector>

#define INF 987654321

using namespace std;


int dist[101][101];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        fill_n(&dist[i][0], n+1, INF);
    }


    for (int i = 0; i < m; i++) {
        int u, v;

        cin >> u >> v;


        dist[u][v] = 1;
        dist[v][u] = 1;
    }


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

    pair<int, int> ans;
    int distA = INF;


    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int temp = 0;
            for (int k = 1; k <= n; k++) {
                int tempI=0;
                int tempJ=0;
                if (i != k) {
                    tempI = dist[i][k];
                }
                if (j != k) {
                    tempJ = dist[j][k];
                }

                temp += min(tempI, tempJ);

            }
            if (distA > temp) {
                distA = temp;
                ans = make_pair(i, j);
            }
        }
    }

    cout << ans.first << " " << ans.second << " " << distA * 2;


    return 0;
}

1. 문제

n개의 건물과 m개의 도로가 있고, 각 도로에 대해 어떤 도시들끼리 연결되어 있는지 주어진다. 각 도로는 이동하는 데 편도 한 시간이 걸린다. 이 중 2개의 건물에 치킨집을 차리는데 다른 모든 건물에 대한 접근성(모든 건물에서 가장 가까운 치킨집까지 왕복하는 최단 시간의 총합)을 최소화하고자 한다. 이 때 치킨집으로 선정할 두 건물과 접근성을 구하여 출력하는 문제이다.

2. 풀이

100개의 건물 중 2개를 골라 나머지 건물에 대한 거리를 구하는 문제이다.

for (int i = 1; i <= n; i++) {
        fill_n(&dist[i][0], n+1, INF);
    }


    for (int i = 0; i < m; i++) {
        int u, v;

        cin >> u >> v;


        dist[u][v] = 1;
        dist[v][u] = 1;
    }

우선 거리 배열을 초기화한 후(dist[i][j]: i 건물로부터 j 건물까지 가는 데 걸리는 시간) 도로를 입력받아 갱신한다. 

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

모든 경우를 확인해야 하므로 all pair shortest path 문제이다. 플로이드 알고리즘으로 모든 거리를 구해준다.

    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int temp = 0;
            for (int k = 1; k <= n; k++) {
                int tempI=0;
                int tempJ=0;
                if (i != k) {
                    tempI = dist[i][k];
                }
                if (j != k) {
                    tempJ = dist[j][k];
                }

                temp += min(tempI, tempJ);

            }
            if (distA > temp) {
                distA = temp;
                ans = make_pair(i, j);
            }
        }
    }

i, j는 각각 치킨집 1과 치킨집 2의 번호이다. 건물 k에서 i, j로 각각 가는 데 걸리는 최소 시간을 구하여 더해준다. 그 후 정답 거리인 distA를 갱신한다.

    cout << ans.first << " " << ans.second << " " << distA * 2;

이 결과를 출력하면 답을 구할 수 있다. 접근성은 왕복으로 걸리는 시간을 계산하므로 2를 곱하여 출력한다.