[SWEA] 점심식사시간

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

SW Expert Academy

 

[풀이]

 

1) 조합 + 시뮬레이션

 

2) 문제를 읽고 단번에 파악할 수 없는 점은 사람들이 항상 가장 가까운 계단으로 가는 것은 아니라는 것이다. (최소 시간이 되는 계단이 꼭 가까이에 있는 계단이 아니기 때문에)

 

3) 그래서 모든 경우의 수를 구해줘야 한다. 다행인 건, 계단이 2개뿐이라는 것이다. (visited로 해결 가능)

- people 백터에 사람들의 위치를 넣어주고 

- stairs 벡터에 계단의 위치를 넣어준다. (distance 계산)

 

4) 1번 계단  / 2번 계단으로 갈 인원들을 구했으면 priority_queue를 사용해서 각 계단으로 넣어준다.

Stairs라는 구조체를 생성해서 각각의 사람들이 내려갈 계단의 번호(stair), 사람들 각자 걸린 시간(time), 계단을 내려가기 시작할 때부터 얼마나 내려왔는지 판단할 변수(wait), 계단과 현재 사람 간의 거리(dist)를 우선순위 큐에 저장한다. 

 

5) 우선순위큐의 정렬 기준은 사람들 각자 걸린 시간이 작은 순서대로, 만약 걸린 시간이 같다면 거리가 짧은 순서대로 정렬되도록 한다. 

 

6) goDownTheStairs()에서는 실제로 사람들을 계단을 내려가도록 한다. 

각각의 계단에는 최대 3명의 사람이 동시에 내려갈 수 있으므로 계단 위에 위치한 사람들의 수를 셀 배열을 생성한다. (계단이 2개이기 때문에)

onStairPeople[2];

 

큐가 비워질 때까지 반복하면서 현재 사람들의 시간을 최소값을 비교할 수 있도록 time 지역변수를 계속 갱신한다.

 

그리고 계단에 현재 사람이 도착했으면 (dist가 시간보다 작거나 같다면 -> 부등호를 넣는 이유는  "계단 입구에 도착하면, 1분 후 아래칸으로 내려 갈 수 있다." 이 조건 때문이다. 계단에 도착하면 일단 1분 쉬어가야 한다.)

 

7) wait가 0이 아니면 이제 계단에 다다랐다는 것이다. 사람들이 계단의 길이만큼 내려오면 큐에서 꺼내줘야 한다.

사람들이 계단을 내려올 때마다 wait를 증가시켜서 wait가 계단의 길이가 되면 큐에서 빼낸다.

 

8) onStairPeople[현재 계단] == 3이면 이미 계단에 사람들이 포화상태이므로 다시 큐에 넣는다. 

그렇지 않다면 onStairPeople[현재 계단] 을 증가해주고 큐에 다시 넣는다. 

 

9) 큐가 비워지면 제일 마지막의 사람까지 모두 내려왔다는 뜻이기 때문에 그때의 최소 시간을 비교해준다.

 

---

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
 
using namespace std;
 
//점심식사시간
int n, map[11][11], ans = 987654321;
typedef pair<int, int> pp;
 
vector<pp> people, stairs;
 
typedef struct Stair {
    int stair, time, wait, dist;
    Stair(){}
    Stair(int _s, int _t, int _w, int _d): stair(_s), time(_t), wait(_w), dist(_d){}
};
 
bool visited[11];
 
bool operator<(Stair a, Stair b) {
    if (a.time == b.time) return a.dist > b.dist;
    return a.time > b.time;
}
void goDownTheStairs(priority_queue<Stair> pq) {
 
    //각 큐에는 가장 빨리? 도착한 사람들 순서대로 저장되어있다. (빨리 도착함= 지금 계단에 있음)
 
    int time = 0, onStairPeople[2]; //계단위에 있는 사람 수를 저장함 (최대 3명)
 
    memset(onStairPeople, 0, sizeof(onStairPeople));
 
    while(!pq.empty()) {
        Stair now = pq.top(); pq.pop();
 
        time = now.time;
        //현재 사람의 시간으로 갱신 
 
        if (now.dist >= time) { //계단에 도착해서 1초 쉬어가야 하기 때문에 부등호를 붙여준다. 
            //아직 계단에 접근하지 못함 -> 다시 넣어줌
            pq.push(Stair(now.stair, now.time+1,now.wait,now.dist));
            continue;
        }
 
        if (now.wait != 0) {
            //이제 계단 내려가는 중 
            //wait가 계단의 길이가 되면 다 내려왔다는 것-> 계단에 있는 사람의 수를 감소시킴 
            //다 내려옴 
            if (now.wait == map[stairs[now.stair].first][stairs[now.stair].second]) {
                onStairPeople[now.stair]--;
                continue;
            }
            pq.push(Stair(now.stair, now.time+1, now.wait+1,now.dist));
            continue;
        }
        if (onStairPeople[now.stair] == 3) { //꽉 차있다.-> 다시 큐에 넣음
            pq.push(Stair(now.stair, now.time+1, now.wait,now.dist));
            // continue;
        }
        else {
            //계단을 내려간다. 
            onStairPeople[now.stair]++;
            pq.push(Stair(now.stair, now.time+1, now.wait+1,now.dist));
            // continue;
        }
    }
    ans = min(ans, time);  
}
void dividePeople() {
    //각 계단마다 사람들을 나눈다. 계단의 개수는 2개 
    //stairs[0], stairs[1];
 
    priority_queue<Stair> pq;
 
    for (int i = 0; i < people.size(); i++) {
        if (visited[i]) {
            // cout << "0번 계단 = " << i << '\n';
 
            int dist = (int)(abs(people[i].first - stairs[0].first) + abs(people[i].second - stairs[0].second));
            pq.push(Stair(0,0, 0, dist));
            
        }
        else {
            // cout << "1번 계단 = " << i << '\n';
            int dist = (int)(abs(people[i].first - stairs[1].first) + abs(people[i].second - stairs[1].second));
            pq.push(Stair(1,0, 0, dist));
 
        }
    }
    
    goDownTheStairs(pq);
}
 
//각 계단으로 갈 조합을 구한다. 
void dfs(int cnt, int cur) {
 
    if (cnt == people.size()) {
        //사람들 다 나눔 
        dividePeople();
    }
 
    // if (cur >= people.size())return;
 
    // for (int i = cur; i < people.size(); i++) {
    //     if (!visited[i]) {
    //         visited[i] = true;
    //         dfs(cnt+1, i+1);
    //         visited[i] = false;
    //     }
    // }
    else {
        visited[cur] = true;
        dfs(cnt+1, cur+1);
        visited[cur] = false;
        dfs(cnt+1, cur+1);
    }
}
 
void init() {
    memset(map, 0, sizeof(map));
    memset(visited, false, sizeof(visited));
    people.clear(); stairs.clear();
    ans = 987654321;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
 
    cin >> t;
 
    for (int tc = 1; tc <= t; tc++)
    {
        cin >> n;
 
        init();
        //초기화 
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
                //1은 사람, 2이상은 계단의 입구 (계단의 길이를 나타낸다.)
                if (map[i][j] == 1) {
                    //사람 
                    people.push_back(pp(i, j));
                }
                else if (map[i][j] > 1) {
                    //계단
                    stairs.push_back(pp(i, j));
                }
            }
        }
        //input
 
        //각 사람들은 모든 계단으로 갈 수 있는 경우의 수를 갖고 있다. -> 가장 가까운 곳만 갈 수 있는 건 아님 
        //완탐 + 조합 
        dfs(0,0);
        dividePeople(); //하나의 계단으로 몰릴 때 -> visited가 모두 false이기 때문에 가능 
 
        cout << "#" << tc << " " << ans << '\n';
    }
 
    return 0;
}