[CodeTree] 병원 거리 최소화하기 (C++) [삼성 SW 역량테스트 기출]

https://www.codetree.ai/training-field/frequent-problems/problems/min-of-hospital-distance

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

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

int n, m, answer = 987654321;
int city[50][50];
bool isUsed[13];

vector<pair<int, int>> patient;
vector<pair<int, int>> hospital;
vector<pair<int, int>> picked;

void dfs(int depth, int start){
    if(depth == m){
        int sum = 0;
        for(int i = 0; i < patient.size(); i++){
            int mindis = 987654321;
            for(int j = 0; j < m; j++){
                mindis = min(mindis, abs(patient[i].first - picked[j].first) + abs(patient[i].second - picked[j].second));
            }
            sum += mindis;
        }
        answer = min(answer, sum);
    } else{
        for(int i = start; i < hospital.size(); i++){
            if(!isUsed[i]){
                isUsed[i] = true;
                picked.push_back({hospital[i].first, hospital[i].second});
                dfs(depth + 1, i + 1);
                picked.pop_back();
                isUsed[i] = false;
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> city[i][j];
            if(city[i][j] == 1) patient.push_back({i, j});
            else if(city[i][j] == 2) hospital.push_back({i, j});
        }
    }
    dfs(0, 0);
    cout << answer;
    return 0;
}

 

 

순열로 병원을 선택할 경우 시간초과 발생 -> 조합으로 선택해야 함 (start)