[백준] 나룻배

https://www.acmicpc.net/problem/2065

2065번: 나룻배

큐, 구현, 시뮬레이션 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

강을 사이에 두고 나룻배가 이동을 하게 됩니다. 이동에는 t의 시간이 걸리고, 만약 정박지에 도착하게 되면 태운 손님을 모두 내려주고, 만약 탈 손님이 있다면 태우고 이동합니다. 만약 도착한 정박지에 손님이 없다면, 그 정박장에서 손님을 기다리고, 이 때 반대쪽 정박장에 손님이 온다면, 그 정박장으로 이동하게 됩니다.

 

<Solution>

문제의 조건들을 정확하게 생각해서 조건을 나누어 시뮬레이션 해야 합니다. 

기본 구성은 다음과 같습니다.

1. 손님들을 left, right queue에 분리한다. 2. 현재 정박지에 탈수있는 사람이 있다면 태운다. 3. 만약 큐가 비었다는 것은 무조건 반대쪽으로 이동해야 한다는 것을 의미 4. 시간이 아직 모자라서 탈 사람이 없는 경우, 양쪽의 queue front를 비교해서 더 빠른 정박장으로 이동해서 손님을 태움

이렇게 4가지 로직을 순차적으로 구성해서 시뮬레이션 하면 됩니다.

 

실제 코드는 아래와 같습니다. 

#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
#define MAXN ((int)1e4)
int M, T, N;//배에태울수있는수, 배이동시간, 손님수
 
struct ppl{
    int AT;
    string SIDE;
    int arrive_time;
};
 
struct ppl ppls[MAXN+10];
 
queue<struct ppl *> q[2]; // 0-> left , 1->right
 
void solution(){
    // queue 채우기
    for(int i = 0; i<N; i++){
        if(ppls[i].SIDE == "left"){
            q[0].push(ppls+i); 
        }
        else{
            q[1].push(ppls+i);
        }
    }
 
    // simulation
    int arrived_ppl_cnt = 0;
    int cur_time = 0;
    int pos_ship = 0; // 0-> left 1-> right
 
    while(arrived_ppl_cnt < N){
        // 1. 현재 정박지에 탈수 있는 사람이 있다면
        if(!q[pos_ship].empty() && q[pos_ship].front()->AT <= cur_time){
            int cnt = 0;
            while(!q[pos_ship].empty() && cnt < M && q[pos_ship].front()->AT <= cur_time){
                q[pos_ship].front()->arrive_time = cur_time+T;
                q[pos_ship].pop();
                arrived_ppl_cnt +=1;
                cnt+=1;
            }
 
            // change position and time
            cur_time+=T;
            pos_ship^=1;
        }
        else{
            // 2. 현재 정박지에 탈수 있는 사람이 없음
            // 2-1. 애초에 queue자체에 사람이 없음
            if(q[pos_ship].empty()){
                pos_ship^=1;
                cur_time = max(cur_time , q[pos_ship].front()->AT);
                cur_time += T;
            }
            // 2-2. 시간때문에
            else{
                // 반대쪽 시간이 더 빠름
                if(!q[pos_ship^1].empty() && q[pos_ship].front()->AT > q[pos_ship^1].front()->AT){
                    pos_ship^=1;
                    cur_time = max(q[pos_ship].front()->AT, cur_time);
                    cur_time+=T;
                }
                else{
                    cur_time = q[pos_ship].front()->AT;
                }
            }
 
        }
 
    }
 
}
 
 
void InputData() {
    cin >> M >> T >> N;
    for (int i = 0; i < N; i++) {
        // cin >> AT[i] >> SIDE[i];
        cin >> ppls[i].AT >> ppls[i].SIDE;
    }
}
void OutputData() {
    for (int i = 0; i < N; i++) {
        cout << ppls[i].arrive_time << "\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
 
    InputData();//입력받는 부분
     
    //여기서부터 작성
    solution();
 
    OutputData();//출력하는 부분
    return 0;
}