[Algorithm] 백준 13424 비밀 모임 - C++, 플로이드-와샬

13424번: 비밀 모임

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;

int roomCount, edgeCount;
int roomDist[101][101];
int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    int testcase;
    cin >> testcase;

    while (testcase--){
        vector<int> friendRooms;
        // input
        cin >> roomCount >> edgeCount;
        for(int i = 1; i <= roomCount; i++){
            for(int j = 1; j <= roomCount; j++){
                if(i == j)
                    roomDist[i][j] = 0;
                
                else 
                    roomDist[i][j] = 999999999;
            }
        }
        for(int i = 0; i < edgeCount; i++){
            int a, b, c;
            cin >> a >> b >> c;

            roomDist[a][b] = c;
            roomDist[b][a] = c;
        }

        int friendCount;
        cin >> friendCount;
        for(int i = 0; i < friendCount; i++){
            int input;  cin >> input;

            friendRooms.push_back(input);
        }


        // floyid
        for(int via = 1; via <= roomCount; via++){
            for(int from = 1; from <= roomCount; from++){
                for(int to = 1; to <= roomCount; to++){
                    if(roomDist[from][to] > roomDist[from][via] + roomDist[via][to])
                        roomDist[from][to] = roomDist[from][via] + roomDist[via][to];
                }
            }
        }

        // search room
        int answer = 999999999;
        int minRoomidx = -1;
        for(int i = 1; i <= roomCount; i++){
            int thisRoomCost = 0;
            for(int j = 0; j < friendRooms.size(); j++){
                thisRoomCost += roomDist[i][friendRooms[j]];
            }

            if(answer > thisRoomCost){
                answer = thisRoomCost;
                minRoomidx = i;
            }
        }

        cout << minRoomidx << '\n';
    }
    
}

---

 플로이드 와샬로 풀이를 하면 간단하게 답이 나왔습니다.

1. 플로이드 와샬로 n-to-n 최단 거리를 만들어 준 뒤

2. 친구들에서 방으로 거리 최소를 구하기

를 무식하게 돌리면 빠르게 답이 나오는 문제입니다.

 

단 테스트케이스가 여러개 있으므로 이에 대한 초기화를 잘 해줘야 2번째 테스트 케이스부터 답이 잘 나오게 됩니다.