[SW Expert 2383] 점심 식사

#문제

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

#풀이

완전 탐색을 통해 푸는 문제이다.

N의 크기가 최대 10에 사람의 수가 최대 10명, 계단의 입구는 반드시 2개이기 때문에 가능하다.

일단, 2개 방식이 떠올랐다.

모든 사람들을 사방으로 움직이며, 계단을 찾았을때 내려가는 방식을 생각해 보았는데... 이건 너무 터무니 없는 짓인것같아서 다른 방법을 생각하였다.

일단 M명의 사람이 어디 계단으로 갈지만 정한 다음 각자의 계단에서 따로 걸리는 시간을 구해주면 되는 방식을 떠올리게 되었다. 이렇게 한다면 계단이 무조건! 2개이므로 사람의 선택지는 2가지 즉 2^M시간이 걸린다.

선택지를 고르고서 계단을 총 내려가는 시간을 구한 다음 두개의 계단을 비교하여 큰 수를 찾아주어야한다.

이유는 첫번째 계단과 두번째 계단은 서로 독립적이기 때문이다.

여기서 '독립적이다'란 말은 무엇일까?

1		1
1			3
	5

위와 같이 4X4의 맵이 있다고 하자.

만약, (1,1)에 있는 사람과, (1,3)에있는 사람은 3이라는 계단으로 간다고 하고, (3,1)에있는 사람은 5라는 계단으로 간다고 하자.

그럼, 우리는 3과 5라는 계단에서 각자 사람들을 내려 보낸다고 한다면 3에서는 7분, 5에서는 8분이 걸리게 된다.

3에서 이미 7분에 끝났다고해도 5 계단에서 끝나지 않았으므로 8분까지 기다려야한다.

이렇기에 두개 모두 시간을 따로 구하고, 둘 중 큰것만 가지고 나머지 경우의 수와 비교를하면 된다.

이제, 내려가는 것이 문제다. 이 내려가는 것을 구현을 어떻게 할지 엄청난 고민과 시간이 걸렸다...

문제에서는 계단에 있을 수 있는 사람의 수는 3명... 즉, 3명이 계단을 내려가고 있다면 다른 사람은 와도 내려갈 수가 없다는것이다.... 뭔..계단이 이따구야.....

문제를 풀어야 하기때문에 참아보며 잘 풀어보자...

일단, 3개의 큐를 만들었다.

하나는 priority queue를 만들어 계단에 도착하는 순서(거리순)으로 정렬된 큐이며, 다른 하나는 계단에 사람을 넣는 큐로서 3명의 사람만 넣을 수 있는 큐이다.

마지막 큐는 기다리는 사람을 넣는 큐로 계단에 3명이 있을 때 들어가는 큐이다.

while문을 돌려 시간을 1분씩 늘려가며 시작한다.

이때, 빠져나가는 조건은 저 3개의 큐가 모두 비워졌을때 가능하다.

계단에 남아있을 수도 있으며, 아직 도착을 못한 사람, 계속해서 기다리는 사람이 있을 수도 있기 때문이다.

먼저 priority queue에서 해당 시간에 도착하는 사람들을 계단 큐로 보내준다.

이때 중요한 점이 있는데, 3명을 넘어서는 안된다는 점과 무조건 바로 계단을 내려가는 것이 아닌 1분을 기다렸다가 내려가기 때문에 내려가는 길이를 +1을 해준다.

또한 같이 도착하는 사람이 있을 수 있으므로 해당 시간에 도착한 사람들은 모두다 계단 큐에 넣어준다.

계단 큐가 3명이 꽉찾을 시에는 웨이팅 큐로 간다. 

priority queue에서 계단 큐로 넘어가듯이 계단 큐에서도 다 내려갈 시간을 구한 뒤 해당 시간에 큐에서 뽑아내는 방식으로 진행된다.

이때도 같이 내려오는 사람이 있을 수있으므로 while문을 돌려주었다.

이후에 만약 계단 큐에 3명의 사람이 없다면, priority queue에서 도착한 사람보다  웨이팅 큐에서 기다린 사람이 먼저 들어가야한다. 세상의 이치 아닐까... 먼저온 사람이 먼저 서비스를 받아야한다...

그렇기에 위에 priority queue에서 계단 큐로 넘어가는 로직보다 위에 있어야한다.

자세한 내용은 코드를 보면 이해가 딱 올것이다.

웨이팅 큐도 이전 큐들과 같이 똑같은 로직을 가지고 있으며 이때는 현재 시간을 넣어주어야 한다.

기다린 시간이 있기 때문이다. 도착하는데 걸리는 시간 + 기다린 시간을 넣어주어 해당 시간이 됬을 때, 계단 큐로 넘어가게된다.(3명이 없을때만!)

위 과정을 돌릴때마다 시간들이 나오며 해당시간을 다른 계단과 비교하여 큰 값을 답과 비교하여 최소 값을 찾으면 끝!!!!!

백준의 치킨문제와 비슷하게 생겨서 쉽게 보고 접근했다가 큰코다쳤다......

그리고 아직까지도 위의 로직을 짜려면 많은 시간이 필요했다.... 정말 노력 많이해야되는데.. 코테는 얼마 남지 안았다...다들 화이팅 하시길 바랍니다...

#코드

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define MAX 10
using namespace std;
 
struct Human{
    int r;
    int c;
    int stair;
};
 
struct Stair{
    int r;
    int c;
};
 
int N;
int ans = 987654321;
int map[MAX][MAX];
vector<Human> humans;
vector<Stair> stairs;
 
int calcDist(Human h, Stair s){
    return abs(h.r - s.r) + abs(h.c - s.c);
}
 
struct cmp{
    bool operator()(int a, int b){
        return a > b;
    }
};
 
int calcTime(int stairNum){
    int totalTime = 0;
    //도착한 사람의 시간 저장
    priority_queue< int, vector<int>, cmp > walkingTime;
    int downTime = map[stairs[stairNum].r][stairs[stairNum].c];
    
    for(int i = 0; i < humans.size(); i++){
        //해당 번호의 계단을 선택했을때만 계산한다.
        if(humans[i].stair == stairNum){
            int dist = calcDist(humans[i], stairs[stairNum]);
            walkingTime.push(dist);
        }
    }
    queue<int> stairQueue;
    queue<int> waitingQueue;
    
    while(true){
        //모든 큐가 비워졌을때 끝마친다.
        if(walkingTime.empty() && stairQueue.empty() && waitingQueue.empty()) break;
        
        totalTime++;
        
        //현재 계단에 사람이 있을때, 내려가는 시간과 계단까지 도착한 시간을 합산했을때가 바로 다 내려갔을때이므로 이동완료.
        if(stairQueue.size() > 0){
            int completeTime = stairQueue.front() + downTime;
            //계단에 같은 시간에 도착했고, 기다리지 않았더라면 다음 값도 같은 시간에 빠져 나와야하므로 계속해서 돌려준다.
            while(totalTime == completeTime){
                stairQueue.pop();
                completeTime = stairQueue.front() + downTime;
                //만약 큐 사이즈가 0일때는 바로 빠져나온다.
                if(stairQueue.size() == 0) break;
            }
            //만약 계단에 3명이 꽉차 있지 않은 상태에서 기다리는 사람이 있다면, 바로 먼저 기다렸던 사람 순대로 넣어준다.
            //이때 중요한점은 현재 시간을 넣어야 된다는 점이다.
            //도착한시간 + 기다린시간 = 현재시간 이기 때문이다.
            if(stairQueue.size() < 3 && waitingQueue.size() > 0){
                //마찬가지로 웨이팅 큐에 아무 값도 없다면 넣어줄 의미가 없으므로 빠져나온다.
                while(stairQueue.size() < 3){
                    stairQueue.push(totalTime);
                    waitingQueue.pop();
                    if(waitingQueue.size() == 0) break;
                }
            }
        }
        //현재시간과 도착한 시간이 맞을 때, stair큐에 넣어준다.
        //만약 stair큐에 원소가 3개 이상이라면 waiting큐에 넣어준다.
        //이때 바로 들어간 사람은 계단 앞에서 1분을 기다리므로 +1을 해준다.
        //여기서도 모든 사람들을 탐색했다면 즉, walkingTime큐에 원소가 없다면 바로 빠져나오도록 해주어야한다.ㅌ
        while(totalTime == walkingTime.top()){
            if(stairQueue.size() >= 3) {
                waitingQueue.push(walkingTime.top());
                walkingTime.pop();
            }else{
                stairQueue.push(walkingTime.top()+1);
                walkingTime.pop();
            }
            if(walkingTime.size() == 0) break;
        }
    }
    return totalTime;
}
 
void selectStair(int manNum){
    //모든 사람이 계단을 고른 경우 시간을 계산
    if(manNum == humans.size()){
        //1번째 계단에서 걸리는 시간과 2번째 계단에서 걸리는 시간을 비교
        //이유는 각각의 계단에서 걸리는 시간은 독립적이기때문에
        //더 많이 걸리는 시간이 최종 시간이 된다.
        int finalTime = 0;
        finalTime = max(calcTime(0), calcTime(1));
        if(ans > finalTime) ans = finalTime;
        return;
    }
    for(int i = 0; i < 2; i++){
        humans[manNum].stair = i;
        selectStair(manNum+1);
    }
}
 
int main(){
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++){
        cin >> N;
        memset(map, 0, sizeof(map));
        ans = 987654321;
        humans.clear();
        stairs.clear();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                cin >> map[i][j];
                if(map[i][j] == 1) {
                    Human h;
                    h.r = i;
                    h.c = j;
                    humans.push_back(h);
                }
                else if(map[i][j] != 0){
                    Stair s;
                    s.r = i;
                    s.c = j;
                    stairs.push_back(s);
                }
            }
        }
        selectStair(0);
        cout << "#" << t << " " << ans << endl;
    }
    return 0;
}