[BOJ] 21278 - 호석이 두 마리 치킨 (C++)

문제

호석이 두 마리 치킨

코드

#include <iostream>
#include <algorithm>
#include <vector>

#define INF 987654321

using namespace std;

int N, M;
int map[101][101], dist[101][101];

bool comp(vector<int>& a, vector<int>& b){
    if (a[2] == b[2]){
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] < b[0];
    }
    return a[2] < b[2];
}

int main(void){
    cin.tie(0); 
    ios_base::sync_with_stdio(false);

    cin >> N >> M;
    
    int x, y;
    for (int i = 0; i < M; i++){
        cin >> x >> y;
        map[x][y] = map[y][x] = 1;
    }

    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            if (i == j) continue;
            dist[i][j] = map[i][j] == 1 ? 1 : INF;
        }
    }

    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]);
            }
        }
    }

    vector< vector<int> > v;
    for (int i = 1; i <= N; i++){
        for (int j = i+1; j <= N; j++){
            int d = 0;
            for (int k = 1; k <= N; k++){
                d += min(dist[k][i], dist[k][j]) * 2;
            }
            vector<int> temp(3,0);
            temp[0] = i; temp[1] = j; temp[2] = d;
            v.push_back(temp);
        }
    }

    sort(v.begin(), v.end(), comp);
    cout << v[0][0] << " " << v[0][1] << " " << v[0][2];
    return 0;
}

접근

일단 N의 최대 값이 100 이고 특정 도시를 거쳐 다른 도시로 이동할 때의 최소 값을 구해야 하기 때문에 플로이드-와샬 알고리즘이 떠올랐다.

1) 먼저 주어진 도로 정보를 이용하여 갈 수 있는 곳과 아닌 곳을 dist 배열에 표시해주었다. (플로이드-와샬)

2) 그 정보를 가지고 모든 경우를 살펴보며 거리의 최소 값을 찾아 건물 정보와 함께 배열에 저장하였다. 

3) 배열에 저장한 후에 원하는 결과가 나올 수 있게 comp 함수를 작성해 주었다. 

결과적으로 답은 배열의 맨 앞에 위치하게 된다.