[SWEA 2383] 점심 식사시간

SWEA 2383번 : 점심 식사시간

swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

/* 문제 설명 */

N*N 배열에 사람(P)들과 2개의 계단 입구(S)가 있다. 

각 사람이 계단 입구까지 도착하려면 이동시간이 | PR - SR | + | PC - SC | 만큼 걸린다.

(PR, PC : 사람 P의 세로위치, 가로위치, SR, SC : 계단 입구 S의 세로위치, 가로위치)

 

계단 입구에 도착한 사람은 1분 후 계단을 내려가는데, 한 층을 내려가려면 1분씩 걸린다.

따라서 계단의 길이가 K면 완전히 내려가는데에는 K분이 걸린다.

 

각 사람들의 위치와 계단 입구 위치와 계단의 길이가 주어졌을 때, 모든 사람들이 계단을 내려가는 시간의 최소를 구하시오.

 

 

/* 해결 방안 */

일단 문제의 조건이 굉장히 많습니다.

정신이 없으니 정리를 해봅시다.

 

ⓐ 여러명의 사람들이 있고, 2개의 계단 입구가 있다.

→ 사람은 1로, 계단은 1보다 큰 수로 이루어져 있다.

ⓑ 계단 입구까지 이동하려면 이동시간이 | PR - SR | + | PC - SC | 만큼 걸린다.

ⓒ 사람이 계단 입구에 도착하면, 1분 후 부터 K 길이의 계단을 내려가기 시작한다.

ⓓ 계단은 동시에 총 3명만 내려갈 수 있다.

ⓔ 3명 중 한 명이 계단을 다 내려갔다면, 입구에서 대기하고 있는 사람이 내려가기 시작한다.

ⓕ 먼저 도착한 사람이 먼저 내려갑니다.

 

BFS라고 생각할 수 있지만, 가까이에 있는 계단을 내려간다고 해서 최소 시간이 보장되지 않습니다.

왜냐하면 계단이 엄청 길 수도 있기 때문입니다.

 

따라서 직접 조합을 구해줘야한다는 것을 알 수 있습니다.

계단 입구가 2개 이므로, 첫 번째 계단으로 가는 사람들의 조합만 구하면 남은 사람들은 자동으로 두 번째 계단으로 가게됩니다.

첫 번째 계단으로 가는 사람들의 수에 대해서 for문을 돌아주고, 직접 조합을 구하면 됩니다!

 

조합을 다 구했으니 이제 시간을 구해봅시다!

우선순위 큐에 한 사람(A)이 계단을 끝까지 내려가는 데 걸리는 시간을 넣어줍니다.

만약 우선순위 큐의 사이즈가 3보다 작으면, 누구든지 계단을 내려갈 수 있습니다.

반면, 우선순위 큐의 사이즈가 3개 이상이면 이미 꽉 차있으므로 대기하는 사람(B)이 생기게 됩니다.

이 때, 현재 내려가고 있는 사람(A)이 걸리는 시간보다 B의 계단 입구 도착 시간이 더 나중이라면,

A는 계단을 다 내려갔으니 바로 B가 들어가면 됩니다.

그 반대라면, B가 계단을 내려가게 되는 시작 시간은 A가 완전히 내려간 후 입니다.

 

/* 구현 과정 */

1. 두 계단에 대하여 사람들의 조합을 구해준다.

2. 우선 순위 큐를 이용해 시간을 구해준다.

 

/* 소스 코드 */

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int, int> pi;
#define INF 1e9
 
int tc, n, m, ans = INF;
vector<pi>v, stair;
vector<int>stair_depth;
bool visited[15];
pi key[15];
 
void findTime(int maxx) {
    int now = 0;
    vector<int>A, B;
 
    for (int i = 0; i < m; i++)
    {
        if (visited[i]) {
            A.push_back(abs(v[i].first - stair[0].first)
                + abs(v[i].second - stair[0].second) + 1);
        }
        else {
            B.push_back(abs(v[i].first - stair[1].first)
                + abs(v[i].second - stair[1].second) + 1);
        }
    }
 
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
 
    int timeA = 0, timeB = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
 
    for (int i = 0; i < A.size(); i++)
    {
        if (pq.size() < 3) pq.push(A[i] + stair_depth[0]);
        else {
            if (pq.top() <= A[i]) {
                pq.push(A[i] + stair_depth[0]);
                pq.pop();
            }
            else {
                int topp = pq.top();
                pq.push(topp + stair_depth[0]);
                pq.pop();
            }
        }
    }
    while (!pq.empty()) {
        timeA = max(timeA, pq.top());
        pq.pop();
    }
 
    for (int i = 0; i < B.size(); i++)
    {
        if (pq.size() < 3) pq.push(B[i] + stair_depth[1]);
        else {
            if (pq.top() <= B[i]) {
                pq.push(B[i] + stair_depth[1]);
                pq.pop();
            }
            else {
                int topp = pq.top();
                pq.push(topp + stair_depth[1]);
                pq.pop();
            }
        }
    }
    while (!pq.empty()) {
        timeB = max(timeB, pq.top());
        pq.pop();
    }
 
    ans = min(ans, max(timeA, timeB));
}
 
 
void func(int x, int k, int maxx) {
    if (k == maxx) {
        int tmp = 0;
        findTime(maxx);
        return;
    }
 
    for (int i = x; i < m; i++)
    {
        if (visited[i]) continue;
        visited[i] = 1;
        func(i + 1, k + 1, maxx);
        visited[i] = 0;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> tc;
    for(int t = 1; t <= tc; t++) {
        cin >> n;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int a; cin >> a;
                if (a == 1) {
                    v.push_back({ i,j });
                    m++;
                }
                else if (a != 0) {
                    stair_depth.push_back(a);
                    stair.push_back({ i,j });
                }
            }
        }
 
        for (int i = 0; i <= m; i++) func(0, 0, i);
 
        cout << "#" << t << " " << ans << "\n";
 
        //init
        fill(visited, visited + 15, 0);
        v.clear(); stair.clear(); stair_depth.clear();
        ans = INF; m = 0;
    }
}

 

 

 

 

 

---