2383 점심 식사시간

처음에 괜히 이것저것 최소화 시키면서 풀려다보니 굉장히 힘들었다.

그치만 맵 크기가 10x10이므로 모든 경우에 대해 탐색해도 실행시간이 얼마 나오지 않는다!

풀이법은 SWExpert의 요리사, 백준의 스타트 링크 문제와 굉장히 비슷하게 풀었다.

1. h벡터에 H 구조체로 x,y 좌표, 출구와의 거리를 저장 시킨다. (사람)

2. e벡터에 E 구조체로 계단의 x,y 좌표, 내려가는데 걸리는 시간을 저장한다. (출구)

3. 1번출구 선택한 팀/ 2번출구 선택한 팀으로 나눠 모든경우에 대해 탐색한다.

4. 결과값을 비교하여 최소값을 출력한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct H {
    int x;
    int y;
    int dist1;
    int dist2;
    H(int x, int y) :x(x), y(y) {}
};
 
struct E {
    int x;
    int y;
    int time;
    E(int x, int y, int t) :x(x), y(y), time(t) {}
};
 
int t, n;
int map[10][10];
 
int calc(vector<int> &v, int t) {
    if (v.size() == 0) return 0;
    //도착시간 기준으로 정렬
    sort(v.begin(), v.end());
    
    //계단 사용중인지 확인하는 배열
    int use[3] = { 0, };
 
    //현재까지 소요된 시간
    int time = v[0];
 
    while (true) {
        for (int i = 0; i < v.size(); i++) {
            //이미 계단을 내려갔다면 continue
            if (!v[i])continue;
            
            //도착시간 확인
            if (v[i] <= time) {
                
                for (int j = 0; j < 3; j++) {
                    //빈 계단이 있는지 확인
                    if (use[j] <= 0) {
                        use[j] = t;
                        v[i] = 0;
                        if (i == v.size() - 1) {
                            return time + t;
                        }
                        break;
                    }
                }
            }
        }
 
        //1초 지난거에 대한 처리
        for (int i = 0; i < 3; i++) {
            use[i]--;
        }
        time++;
    }
}
 
int getTime(int check, vector<H> &h, vector<E> &e) {
    vector<int> A; //1번출구 선택
    vector<int> B; //2번출구 선택
    for (int i = 0; i < h.size(); i++) {
        if (check & (1 << i)) A.push_back(h[i].dist1);
        else B.push_back(h[i].dist2);
    }
 
    return max(calc(A, e[0].time), calc(B, e[1].time));
}
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++) {
        cin >> n;
 
        vector<H> h;
        vector<E> e;
        int x;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> x;
                if (x == 1) h.push_back(H(i, j));
                else if (x > 1)e.push_back(E(i, j, x));
            }
        }
        //출구들과 거리 계산하기
        for (int i = 0; i < h.size(); i++) {
            h[i].dist1 = abs(h[i].x - e[0].x) + abs(h[i].y - e[0].y);
            h[i].dist2 = abs(h[i].x - e[1].x) + abs(h[i].y - e[1].y);
        }
 
        //완전 탐색
        int res = 987654321;
        for (int i = 0; i < (1 << h.size()); i++) {
            res = min(res, getTime(i, h, e));
        }
 
        cout << "#" << tc << " " << res + 1 << endl;
    }
}