[C++] 삼성 2383. [모의 SW 역량테스트] 점심 식사시간

#include<iostream>
#include<vector>
#include<math.h>
#include<string.h>
#include<algorithm>
 
using namespace std;
 
#define PII pair<int, int>
#define INF 99999999
 
int min_dist;
int arr[11][11];
vector<PII> peoples;
vector<pair<PII, int>> stairs;
 
int cal_dist(pair<int, int> a, pair<int, int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}
 
int cal_stairs(vector<PII> stairs1, vector<PII> stairs2) {
    int stairs1_size = stairs1.size();
    int stairs2_size = stairs2.size();
    int stairs1_time = 0;
    int stairs2_time = 0;
 
 
    for (int i = 3; i < stairs1_size; i++) {
        if ((stairs1[i - 3].first + stairs1[i - 3].second) > stairs1[i].first)
            stairs1[i].first = stairs1[i - 3].first + stairs1[i - 3].second;
    }
 
    if (stairs1_size != 0)
        stairs1_time = stairs1[stairs1_size - 1].first + stairs1[stairs1_size - 1].second;
 
 
    for (int i = 3; i < stairs2_size; i++) {
        if ((stairs2[i - 3].first + stairs2[i - 3].second) > stairs2[i].first)
            stairs2[i].first = stairs2[i - 3].first + stairs2[i - 3].second;
    }
 
    if (stairs2_size != 0)
        stairs2_time = stairs2[stairs2_size - 1].first + stairs2[stairs2_size - 1].second;
 
    return max(stairs1_time, stairs2_time);
}
 
void lunch_time(int index, vector<PII> stairs1, vector<PII> stairs2) {
    if (index == peoples.size()) {
        sort(stairs1.begin(), stairs1.end());
        sort(stairs2.begin(), stairs2.end());
        int dist = cal_stairs(stairs1, stairs2);
        //cout << "stair1 : " << stairs1.size() << " stairs2 : " << stairs2.size() << " dist : " << dist << endl;
        if (min_dist > dist)
            min_dist = dist;
        return;
    }
 
    stairs1.push_back(PII(cal_dist(peoples[index], stairs[0].first)+1, stairs[0].second));
    lunch_time(index + 1, stairs1, stairs2);
    stairs1.pop_back();
    stairs2.push_back(PII(cal_dist(peoples[index], stairs[1].first)+1, stairs[1].second));
    lunch_time(index + 1, stairs1, stairs2);
    stairs2.pop_back();
}
 
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        memset(arr, 0, sizeof(arr));
        min_dist = INF;
        int N;
        cin >> N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> arr[i][j];
                if (arr[i][j] == 1)
                    peoples.push_back(make_pair(i, j));
                else if (arr[i][j] > 1)
                    stairs.push_back(make_pair(make_pair(i, j), arr[i][j]));
            }
        }
        vector<PII> stairs1;
        vector<PII> stairs2;
        lunch_time(0, stairs1, stairs2);
        cout << "#" << t << " " << min_dist << endl;
        peoples.clear();
        stairs.clear();
    }
    return 0;
}