[DFS] SWEA2383 점심 식사시간

문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl&categoryId=AV5-BEE6AK0DFAVl&categoryType=CODE

 

Solution

• DFS로 각 사람이 내려갈 계단을 선택하고, 각 계단에서 모든 사람이 내려가는 시간을 구해 그 중 최소가 되는 순열을 구한다.

Point

• 각 사람이 내려갈 계단을 어떻게 선택해야하는 지를 생각하는 것이 까다로웠는데, 결론적으로 계단이 2개 뿐이기 때문에 모든 경우의 수를 고려해도 2^N이 되고 N<=10이기 때문에 최대 1024 가지의 경우의 수를 가진다. 따라서 모든 경우의 수를 DFS로 탐색해보아도 시간 안에 문제를 풀 수 있기 때문에 가지치기 없이 모든 경우를 DFS 탐색하면 된다.
• 계단 내려가는 시간 구할 때, 먼저 각 사람이 해당 계단까지 내려가는 거리를 구해 이를 기반으로 pq에 넣어 min heap을 만들고, 거리가 짧아 먼저 도착한 사람부터 한번에 3명씩 차례로 내려가게 해서 시간을 구한다.

---

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

using namespace std;

typedef struct Person {
    int id, x, y, time, s, dist; //s:stair id
}Person;

struct compare
{
    bool operator()(const Person & a, const Person & b)
    {
        return a.dist > b.dist;
    }
};

typedef struct Stair {
    int x, y, k;
    priority_queue<Person, vector<Person>, compare> q;
}Stair;

int T, N, result;
int dx[4] = { 1, -1, 0 , 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<Person> people;
vector<Stair> stairs;

void input() {
    result = 987654321;
    people.clear();
    stairs.clear();
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int n;
            cin >> n;
            if (n == 1) people.push_back({ (int)people.size(), i, j, 0, 0, 0 });
            else if (n > 1) stairs.push_back({ i, j, n });
        }
    }
}

int countTime() {
    int rt = 0;
    for (int i = 0; i < people.size(); i++) {
        people[i].dist = abs(people[i].x - stairs[people[i].s].x) + abs(people[i].y - stairs[people[i].s].y);
        people[i].time = abs(people[i].x - stairs[people[i].s].x) + abs(people[i].y - stairs[people[i].s].y);
        stairs[people[i].s].q.push(people[i]);
    }
    for (int i = 0; i < stairs.size(); i++) {
        int count = 0;
        int prev[3] = { 0 }; //three people getting down
        while (!stairs[i].q.empty()) {
            Person cur_p = stairs[i].q.top();
            stairs[i].q.pop();
            if(cur_p.time < prev[count % 3])
                cur_p.time = prev[count % 3] + stairs[i].k;
            else
                cur_p.time += stairs[i].k + 1;
            prev[count % 3] = cur_p.time;
            rt = max(rt, prev[count % 3]);
            count++;
        }
    }
    return rt;
}

void dfs(int d) {
    if (d == people.size()) {
        result = min(countTime(), result);
        return;
    }
    for (int i = 0; i < stairs.size(); i++) {
        people[d].s = i; //choose a stair
        dfs(d + 1);
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    cin >> T;
    for (int t = 1; t <= T; t++) {
        input();
        dfs(0);
        cout << "#" << t << " " << result << endl;
    }
}