[데이터구조] #Mission 2, 놀이기구

문제, 최소히프(Min Heap)를 이용하여 아래 시물레이션 프로그램을 자성하시오.

■ 놀이공원의 A 놀이기구는 오전 10시부터 오후 2시까지 운행한다.

■ 최대 탑승인원은 30명이나, 반드시 인원을 모두 채워 운행할 필요는 없다

■ 1회 운행 시 소요되는 시간은 7-12분으로 uniform distribution을 따른다. (Uniform distribution은 rand( ) 함수 사용하면 가능)

■ 이 놀이기구를 조종하는 직원의 시급은 6000원이다.

■ 이용객 1인의 1회 이용 비용은 2000원이다.

■ 이용객은 3-8명씩 그룹으로, 1-3분 간격으로 도착하며, 모두 uniform distribution을 따른다.

■ 그룹 이용객은 모두 탑승하거나, 다음 차례를 기다린다.

■ 미탑승으로 인해 생긴 빈자리는 후순위 이용객에게 돌아가지 않는다. (예를들어 빈자리가 4자리인 경우, 탑승 최우선순위 그룹이 5명이면, 이 그룹은 탑승하지 않으며, 차우선순위 그룹이 4명 이하여도 탑승하지 않는다.)

■ 이용객이 차례를 기다리다가 그냥 가는 예외 상황은 발생하지 않는다고 가정한다.

■ 1일 간 이 놀이기구에서 벌어들인 수입을 계산하시오.

-알고리즘

-code

#include <stdio.h>
#include <stdlib.h>
 
#define TRUE   1
#define FALSE   0
 
#define ARRIVAL 1
#define START   2
 
int group = 0;             //놀이기구를 탑승하는 그룹 수
int free_seats = 30;        //잔여좌석
int start = 0;            //운행시간
int sum = 0;            //하루 총 손님 수
float current_profit = 0;        //운행할 때 증가된 수익
float profit = 0;            //현재 총 수익
int i = 0;
int cur[1000] = { 0 };        //대기자들을 저장하기 위한 배열
int s_group = 0;           //하루 총 그룹 수 
int back_number = 0;        //환불 받아야 하는  손님 수
int back_group = 0;
#define MAX_ELEMENT 1000
typedef struct {
    int type;              //이벤트의 종류
    int time;                 //이벤트가 일어난 시각
    int number;            //고객의 숫자
}element;
 
typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
}HeapType;
 
//초기화 함수
void init(HeapType *h)
{
    h->heap_size = 0;
}
 
int is_empty(HeapType *h)
{
    if (h->heap_size == 0)
        return TRUE;
    else
        return FALSE;
}
 
//삽입함수
void insert_min_heap(HeapType *h, element item)
{
    int i;
    i = ++(h->heap_size);
    // 트리를 거슬러 올라가면서 부모 노드와 비교하는 과정
    while ((i != 1) && (item.time < h->heap[i / 2].time))
    {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    h->heap[i] = item;   //새로운 노드를 삽입
}
 
//삭제함수
element delete_min_heap(HeapType *h)
{
    int parent, child;
    element item, temp;
 
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent = 1;
    child = 2;
 
    while (child <= h->heap_size)
    {
        //현재 노드의 자식 노드 중 더 작은 자식 노드를 찾는다.
        if ((child<h->heap_size) && (h->heap[child].time) > h->heap[child + 1].time)
        {
            child++;
        }
        if (temp.time <= h->heap[child].time)
        {
            break;
        }
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    h->heap[parent] = temp;
    return item;
}
 
// 0에서 n사이의 정수 난수 생성 함수
int random(int n)
{
    return (int)(n*rand() / (double)RAND_MAX);
}
void remain(int number)
{
    cur[i] = number;
    i++;
}
 
//자리가 가능하면 빈자리 수를 사람 수만큼 감소시키다.
int is_seat_available(int number, int time) //잔여좌석을 판단하는 함수
{
    if (free_seats >= number) //잔여좌석이 인원수보다 많을 때(탑승가능할 때)
    {
        group++;    //탐승 그룹 수를 하나씩 증가
        free_seats -= number;     //잔여좌석을 인원 수 만큼 빼준다
        back_number = 0;        //탑승하였기 때문에 환불하지 않아도 된다
        back_group = 0;
        return TRUE;        //1반환
 
    }
 
    if (free_seats < number || i != 0) //잔여좌석이 인원보다 적을 경우(탑승 불가능) 혹은 i는 대기자를 확인하는 배열의 번호이다, i!=0은 값이 존재할 때이므로 대기자가 있는 경우
    {
        remain(number);    //대기자를 저장하는 함수
    }
    return FALSE;
}
 
//이벤트를 처리한다.
void process_event(HeapType *heap, element e)
{
    int j;
    element new_event;
 
    switch (e.type)
    {
    case ARRIVAL:    //도착일 경우
        if (e.time <= start) //운행시간보다 손님도착시간이 더 빠를 때
        {
            printf("%d명의 손님도착. 도착시간:%d \n", e.number, e.time);
        }
        back_number += e.number;//일단 손님이 도착하면 명수를 넣어주고 출발할때, 출발하면 초기화 아니면 환불
        back_group++;
        new_event.type = START;        //출발경우
        new_event.time = e.time;        //도착시간과 같은 값으로
        new_event.number = e.number;    //이용하는 손님 수를 같은 값으로
        insert_min_heap(heap, new_event);
        break;
 
    case START:      //출발일 경우(놀이기구 운행출발)
        if (e.time <= start)    //손님의 도착시간이 운행시간보다 더 빠를 때 
        {
            is_seat_available(e.number, e.time); //잔여좌석 판단하는 함수
        }
        else if (start <= e.time)    //손님의 도착시간이 운행시간보다 더 느릴 때
        {
            back_number = 0;        //운행시작이므로 환불하지 않아도 된다
            back_group = 0;
            printf("** 잔여좌석:%d개 **\n", free_seats);    //잔여좌석 출력
            sum += 30 - free_seats;    //30-free_seats는 운행할때마다의 탑승한 손님 수 이므로 sum=sum+30-free_seats은 하루 동안 탑승하는 손님들의 총 수이다
            printf("** %d개 그룹이 탑승하였습니다. 운행시작:%d분 **\n", group, start);
            s_group += group;    //하루 동안 이용하는 총 손님 그룹의 수
            current_profit = 2000 * (30 - free_seats);        //운행할때마다 증가되는 수익
            profit += current_profit;    //하루 동안 벌어들인 수익
            start += 7 + random(5);    //다음 운행시간의 입력해준다
            free_seats = 30;     //다음 운행을 위한 잔여좌석의 초기화
            group = 0;    //다음 운행만의 그룹 수를 측정해야 하므로 그룹 수를 초기화
            printf("-%.2f원 수익이 늘었습니다. \n", current_profit);    //늘어난 수익 출력
            printf("-현재 수익:%.2f\n", profit);    //현재까지의 수익 출력
            if (i != 0)    //대기자를 저장한 배열이 비어 있지 않을 때
            {
                printf("%d그룹대기\n", i);    //대기하는 그룹 수 출력
            }
            current_profit = 0;    //다음 운행 시에 늘어난 수익만을 측정하기 위해 수익 초기화 
 
            for (j = 0; j<i; j++)    //대기자 배열을 하나하나 출력하고 잔여좌석 계산 
            {
                printf("<%d명>", cur[j]);    //대기자 그룹 각각의 대기 인원 수 출력
 
                if (free_seats >= cur[j])    //대기자 인원수가 잔여좌석보다 적을 때
                {
                    free_seats -= cur[j];    //대기자들을 다음 운행에 넘기려면 잔여좌석을 대기자들 수만큼 빼주어야 한다
                }
                group++;    //대기자 그룹이 다음 운행에 탔으므로 놀이기구를 탄 그룹 수 증가 
                back_number += cur[j];    //다음 운행이 마감시간일 수도 있기 때문에 환불을 위해 사람 수를 저장해 준다
                back_group++;    //윗줄과 마찬가지로 환불을 위한 그룹 수 증가
            }
            i = 0;    //대기자 배열을 비웠으므로 다시 배열을 초기화
            printf("\n");
        }
        profit += current_profit;    //운행마다 벌어들이는 수익을 모두 저장하면 하루 동안 벌어들인 수익계산 가능
        break;
    }
 
}
int main()
{
    element event;
    HeapType heap;
    unsigned int t = 0;
 
 
    init(&heap);
    // 처음에 몇 개의 초기 이벤트를 생성시킨다.
    while (t<240)    //시간은 오전10시~오후2시, 분으로 계산하여 240분
    {
        t += 1 + random(3);    //이용객은 1~3분 간격으로 도착한다
        event.type = ARRIVAL;    //도착 이벤트 
        if (t<240)    //시간이 영업시간일때
        {
            event.time = t;        //이벤트의 시간은 이용객이 1~3분 간격으로 도착하는 시간
        }
        event.number = 3 + random(6);    //이용객은 한 그룹 당 3~8명씩 도착한다
        insert_min_heap(&heap, event);     //이벤트 삽입함수
    }
    start = 7 + random(5);        //첫 운행시간 7~12분 사이
 
    while (!is_empty(&heap))    //힙이 비어있지 않을 때
    {
        event = delete_min_heap(&heap);    //삭제함수
        process_event(&heap, event);
    }
    printf("%d명,%d개 그룹이 운행시간이 지나 탑승하지 못했습니다 .총환불%d원 \n", back_number, back_group, back_number * 2000);
    printf("총 %d명 총 %d그룹이 이용하였고", sum, s_group);
    printf("전체 순익은 %.2f원입니다.\n", profit - 6000 * 4 - back_number * 2000);
}

-결과

	☞운행처음  6명, 7명, 5명, 8명의 손님들이(현재 총 26명) 그룹을 지어서 차례대로 도착하고 마지막 7명 손님들은 잔여좌석이(4개)가 부족하므로 대기자열로 넘어간다. 운행시간은 7~12분 사이로(start=7+random(5)) 4개 그룹이 탑승하였고 운행시작 시간은 9분이다. 26명이 탑승하였으므로 26*2000(1인당 이용요금)=52000원 수익이 늘었고 첫 운행이므로 현재까지의 수익도 52000원이다. 마지막에 도착하였던 7명이 있기 때문에 1그룹이 대기 중이고 다음 운행으로 넘어가서 잔여좌석은 30-7=23개부터 시작된다.
	☞운행중간  34분에 운행되는 중간운행에는 6명, 5명, 6명, 7명,4명의 손님이 차례대로 도착하였고 총 28명의 손님, 5개의 그룹이 탑승하였다.
	☞운행 마지막  221분에 시작되는 운행에 4개 그룹이 탑승하였고 놀이기구가 운행이 시작이 되고 나서 2그룹 <6명><5명>이 대기중인 것을 확인할 수 있다.  그 대기그룹 들은 다음 운행에 넘어가고 잔여좌석은 대기인원수를 뺀 30-(6+5)=19개부터 시작된다. 238분에 운행되는 마지막 운행에서 5명, 6명의 그룹 2개가 도착하였고 그러므로 잔여좌석은 19개가 된다. 11*2000=22000원 수익이 늘었고 마지막 운행 시간이 지나서 온 손님은 없으므로 환불은 0원이고 하루 동안 이 놀이기구를 이용한 손님수는 503명이고 그룹수는 92개이고 전체 순익은 503*2000-6000*4(알바생의 알바비)=982000원이다.