[SWEA] 점심 식사시간

[SWEA] 점심 식사시간

Problem URL : 점심 식사시간

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

using namespace std;

int n;
int peopleNum;
int answer;
int checkPeople[10][2];

struct Person {
    int x;
    int y;
    int target;
    int distance[2];
    int distDiff;
    Person(int _x, int _y) : x(_x), y(_y) {};
};

struct Stair {
    int x;
    int y;
    int value;
    Stair(int _x, int _y, int _value) : x(_x), y(_y), value(_value) {};
};

vector <Person> people;
vector <Stair> stairs;

int distance(Person person, Stair stair) {
    int x = abs(person.x - stair.x);
    int y = abs(person.y - stair.y);

    return x + y;
}

bool cmp(const Person& a, const Person& b)
{
    if (a.distDiff > b.distDiff) return true;
    return false;
}

void dfs(int idx) {
    if (idx == peopleNum) {
        vector <int> stairPeople[2];
        int stairLength[2];
        stairLength[0] = stairs[0].value;
        stairLength[1] = stairs[1].value;

        for (int i = 0; i < peopleNum; i++) {
            int stairNum = people[i].target;
            int tmp = people[i].distance[stairNum] + stairLength[stairNum] + 1;
            if (tmp > answer) {
                checkPeople[i][stairNum] = 1;
                return;
            }
            stairPeople[stairNum].push_back(tmp);
        }

        int size[2]; 
        size[0] = stairPeople[0].size();
        size[1] = stairPeople[1].size();

        int answerTmp = 0;

        for (int i = 0; i < 2; i++) {
            if (size[i] > 0) {
                sort(stairPeople[i].begin(), stairPeople[i].end());
                if (size[i] >= 4) {
                    for (int j = 3; j < size[i]; j++) {
                        int watingTime = stairPeople[i][j - 3] + stairLength[i] - stairPeople[i][j];
                        if (watingTime > 0) {
                            stairPeople[i][j] = stairPeople[i][j] + watingTime;
                        }
                    }
                }
                answerTmp = answerTmp < stairPeople[i].back() ? stairPeople[i].back() : answerTmp;
                if (answerTmp > answer) {
                    return;
                }
            }
        }

        answer = answer < answerTmp ? answer : answerTmp;

    } else {
        if (people[idx].distance[0] > people[idx].distance[1]) {
            people[idx].target = 1;
            if (!checkPeople[idx][1]) {
                dfs(idx + 1);
            }
            people[idx].target = 0;
            if (!checkPeople[idx][0]) {
                dfs(idx + 1);
            }
        } else {
            people[idx].target = 0;
            if (!checkPeople[idx][0]) {
                dfs(idx + 1);
            }
            people[idx].target = 1;
            if (!checkPeople[idx][1]) {
                dfs(idx + 1);
            }
        }
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC;
    cin >> TC;

    for (int tc = 1; tc <= TC; tc++) {
        answer = 2e9;
        cin >> n;
        people.clear();
        stairs.clear();
        memset(checkPeople, 0, sizeof(checkPeople));
        int tmp;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> tmp;
                if (tmp == 1) {
                    people.push_back(Person(i, j));
                } else if (tmp > 1) {
                    stairs.push_back(Stair(i, j, tmp));
                }
            }
        }

        peopleNum = people.size();

        // people 초기화
        for (int i = 0; i < peopleNum; i++) {
            int distance0 = distance(people[i], stairs[0]);
            int distance1 = distance(people[i], stairs[1]);
            people[i].distance[0] = distance0;
            people[i].distance[1] = distance1;
            people[i].distDiff = abs(distance0 - distance1);
        }

        // distDiff가 큰것부터 처리하도록 정렬
        // distDiff가 높을수록 가까운 계단이 최적해일 확률이 높다.
        sort(people.begin(), people.end(), cmp);
        dfs(0);
        cout << "#" << tc << " " << answer << endl;
    }

    return 0;
}