[실압코] 큐 (queue)

들어가며

 오늘은 자료구조 큐(queue)에 대하여 알아보겠습니다. 큐의 개념과 C++에서 큐를 쓰는 방법과 자주 쓰는 메서드, 큐를 활용한 문제까지 하나 풀어보겠습니다.

큐

 큐는 저번에 소개한 스택과 반대로 먼저 들어간 원소가 먼저 나오는 First-In First-Out(FIFO) 자료구조입니다. 식당에서 먼저 주문이 들어온 음식이 먼저 나오듯이 큐에서도 먼저 푸시한 원소가 먼저 팝 됩니다.

#include <queue>

using namespace std;

int main()
{
    queue<int> que;
    que.front();    // 가장 먼저 삽입된 원소
    que.back();     // 가장 나중에 삽입된 원소
    que.push(10);   // 큐의 back에 원소를 삽입
    que.pop();      // 큐의 front에서 원소를 삭제
    que.size();     // 큐가 가지고 있는 원소의 개수
    que.empty();    // 큐가 비어있는지

    return 0;
}

문제

• 백준 2065. 나룻배

 손님이 정박장에 도착하는 시간과 도착하는 정박장의 위치가 주어졌을 때 각 손님이 목적지에 도착하게 되는 시간을 출력하면 되는 문제입니다. left, right에 각각 하나씩 두 개의 큐를 이용하여 문제를 해결할 수 있습니다.

 풀이방법은 다음과 같습니다. 현재 시간과 현재 위치를 기준으로 조건에 맞게 행동하면 됩니다.

• 현재 위치에 태울 손님이 있는 경우
  • 현재 시간에 태울 수 있는 손님 최대 M명 처리
  • 현재 위치와 시간을 업데이트
• 현재 위치에 태울 손님이 없는 경우
  • 반대쪽 위치에 태울 손님이 있는 경우
    • 반대쪽으로 이동
    • 현재 위치와 시간을 업데이트
  • 반대쪽 위치에 태울 손님이 없는 경우
    • 현재 위치에 다음 손님이 먼저 도착하는 경우
      • 손님이 도착할때까지 기다림
      • 현재 시간에 태울 수 있는 손님 최대 M명 처리
      • 현재 위치와 시간을 업데이트
    • 반대쪽 위치에 다음 손님이 먼저 도착하는 경우
      • 손님이 도착할때까지 기다림
      • 반대쪽으로 이동
      • 현재 위치와 시간을 업데이

// BOJ 2065. 나룻배
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>

using namespace std;

struct Info
{
    int arrive;
    int idx;
    bool isLeft;

    void fill(int a, int i, bool l)
    {
        arrive = a;
        idx = i;
        isLeft = l;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int M, t, N;
    cin >> M >> t >> N;

    vector<Info> origin(N); // 출발시간, 입력 인덱스, 왼쪽 출발
    queue<pair<int, int>> left, right; // 출발시간, 입력 인덱스
    vector<int> ans(N); // 도착시간

    for (int i = 0; i < N; i++)
    {
        int a; // 출발 시간
        string b; // 왼쪽 출발

        cin >> a >> b;

        if (b == "left")
            origin[i].fill(a, i, true);
        else
            origin[i].fill(a, i, false);
    }

    // 출발 시간순으로 정렬
    sort(origin.begin(), origin.end(), [](const Info& a, const Info& b) { return a.arrive < b.arrive; });

    for (int i = 0; i < N; i++)
    {
        if (origin[i].isLeft)
            left.push({ origin[i].arrive, origin[i].idx });
        else
            right.push({ origin[i].arrive, origin[i].idx });
    }

    int currT = 0; // 현재 시간
    bool isLeft = true; // 현재 왼쪽

    while (!left.empty() || !right.empty())
    {
        if (left.empty())
        {
            while (!right.empty())
            {
                // 손님이 올 시간이 안됐다면 시간이 지나감
                if (currT < right.front().first)
                {
                    currT = right.front().first;
                }

                // 배가 왼쪽에 있으면 옮김
                if (isLeft)
                {
                    currT += t;
                    isLeft = false;
                }

                // 현재 시간에 태울 수 있는 최대 M명의 손님 처리
                for (int i = 0; i < M && !right.empty() && right.front().first <= currT; i++)
                {
                    ans[right.front().second] = currT + t; // 건너는데 t시간
                    right.pop();
                }

                // 배 왼쪽으로 이동
                currT += t;
                isLeft = true;
            }

            continue;
        }

        if (right.empty())
        {
            while (!left.empty())
            {
                // 손님이 올 시간이 안됐다면 시간이 지나감
                if (currT < left.front().first)
                {
                    currT = left.front().first;
                }

                // 배가 오른쪽에 있으면 옮김
                if (!isLeft)
                {
                    currT += t;
                    isLeft = true;
                }

                // 현재 시간에 태울 수 있는 최대 M명의 손님 처리
                for (int i = 0; i < M && !left.empty() && left.front().first <= currT; i++)
                {
                    ans[left.front().second] = currT + t; // 건너는데 t시간
                    left.pop();
                }

                // 배 오른쪽으로 이동
                currT += t;
                isLeft = false;
            }

            continue;
        }

        if (isLeft)
        {
            if (left.front().first <= currT) // 현재 태울 손님이 있음
            {
                // 현재 시간에 태울 수 있는 최대 M명의 손님 처리
                for (int i = 0; i < M && !left.empty() && left.front().first <= currT; i++)
                {
                    ans[left.front().second] = currT + t; // 건너는데 t시간
                    left.pop();
                }

                // 배 오른쪽으로 이동
                currT += t;
                isLeft = false;
            }
            else // 현재 태울 손님이 없음
            {
                if (right.front().first <= currT) // 오른쪽에 대기손님 있음
                {
                    currT += t; // 오른쪽으로 이동
                    isLeft = false;
                }
                else if (left.front().first <= right.front().first) // 왼쪽에 손님이 먼저 도착
                {
                    currT = left.front().first;
                }
                else // 오른쪽에 먼저 도착
                {
                    currT = right.front().first + t; // 오른쪽으로 이동
                    isLeft = false;
                }
            }
        }
        else
        {
            if (right.front().first <= currT) // 현재 태울 손님이 있음
            {
                // 현재 시간에 태울 수 있는 최대 M명의 손님 처리
                for (int i = 0; i < M && !right.empty() && right.front().first <= currT; i++)
                {
                    ans[right.front().second] = currT + t; // 건너는데 t시간
                    right.pop();
                }

                // 배 왼쪽으로 이동
                currT += t;
                isLeft = true;
            }
            else // 현재 태울 손님이 없음
            {
                if (left.front().first <= currT) // 왼쪽에 대기손님 있음
                {
                    currT += t; // 왼쪽으로 이동
                    isLeft = true;
                }
                else if (right.front().first <= left.front().first) // 오른쪽에 손님이 먼저 도착
                {
                    currT = right.front().first;
                }
                else // 왼쪽에 먼저 도착
                {
                    currT = left.front().first + t; // 왼쪽으로 이동
                    isLeft = true;
                }
            }
        }
    }

    for (int i = 0; i < N; i++)
        cout << ans[i] << '\n';

    return 0;
}

마치며

 오늘은 자료구조 큐에 대해서 다루어 봤습니다. 오늘 예시로 한 문제처럼 시간에 흐름에 따라 시뮬레이션하는 문제에서 큐를 사용하면 편리합니다. 감사합니다.