병원 시뮬레이션 < 순환 큐, 우선순위 큐 > (Hospital Simulation < Circular Queue, Priority Queue >)

Rules

  • 병원에는 진료실, 응급실, 수술실, 회복실, 그리고 영안실이 각각 한 개씩 있다.

  • 일반 환자의 경우 진료실에서 진료를 받고 회복실로 가기 위해 대기한다.

    • 일반 환자는 random 하게 진료실에 도착한다. (random number generation)
    • 진료실에 먼저 온 환자가 먼저 회복실로 갈 수 있다. (FIFO rule)
    • 진료실을 위한 데이터구조는 circular queue 이다.
  • 출혈이 심한 응급 환자는 응급실에서 응급처치를 받고 수술실로 가기 위해 대기한다.

    • 응급 환자는 random 하게 응급실에 도착한다.
    • 출혈량(b)은 환자가 응급실에 도착할 때 random 하게 부여된다. (min  b  max)
    • 환자의 출혈량은 단위시간이 지남에 따라 일정량 만큼씩 증가한다.
    • 출혈량이 많은 환자일수록 높은 우선순위가 부여된다.
    • 우선 순위가 가장 높은 환자가 먼저 수술실에 들어갈 수 있다.
    • 우선 순위가 같은 경우는 FIFO rule 을 따른다.
    • 과다 출혈(b > max)로 사망한 환자는 수술실 대신 바로 영안실로 옮긴다.
    • 응급실을 위한 데이터구조는 priority queue(max heap)이다.
  • 응급 처치가 끝난 환자는 수술실로 옮겨져 수술을 받는다.

    • 수술실은 한 번에 한 명의 환자만을 수용할 수 있다.
    • 수술 시간은 수술을 받는 모든 환자에게 동일하다고 가정한다.
  • 진료가(수술이) 끝난 후에 환자는 회복실로 옮겨져 안정을 취한다.

    • 회복실은 한 번에 한 명의 환자만을 수용할 수 있다.
    • 응급 환자가 일반 환자 보다 먼저 회복실에 들어갈 수 있다. (동시 발생의 경우)
    • 회복 시간은 환자 유형별(응급/일반)로 다를 수 있다.
    • 환자 유형이 같은 경우 회복 시간은 동일하다고 가정한다.
  • 환자가 회복실에서 나오면 바로 퇴원한다.

  • 시뮬레이터는 다음 사항을 주의해야 한다.

    • 시뮬레이션 시간은 정수 값으로 시작부터 종료 시까지 단위시간으로 증가한다.
    • 시뮬레이터는 응급 환자가 응급실을 나올 때까지는 사망 여부를 알 수 없다.
  • 프로그램 작성을 위해 필요한 기타 사항은 일반성의 범주 내에서 각자 정의한다.

Sample

모든 입력 값은 positive integer 임.

[Program Input] – input.txt

100 // 시뮬레이션을 위한 총 단위 시간
5 // 응급 환자의 수술 시간
3 // 응급 환자의 회복 시간
2 // 일반 환자의 회복 시간
10 // 응급 환자의 최대 출혈량 (max)
0 // 응급 환자의 최소 출혈량 (min)
2 // 응급 환자의 단위 시간 당 출혈량
35 // 단위 시간 당 일반 환자의 발생 확률 (percentage)
65 // 단위 시간 당 응급 환자의 발생 확률 (percentage)

[Program Output] – output.txt

1. 병원에 온 환자의 총 수
2. 병원에서 퇴원한 일반 환자의 수
3. 병원에서 퇴원한 응급 환자의 수
4. 과다출혈로 사망한 환자의 수
5. 진료실 환자의 진료실 평균 대기 시간
6. 응급실 환자의 응급실 평균 대기 시간
7. 진료실에 남아 있는 일반 환자의 수
8. 응급실에 남아 있는 응급 환자의 수
9. 수술실에서 수술중인 응급 환자의 존재 여부
10. 회복실에서 회복중인 환자(응급/일반)의 존재 여부

Source Code

main.cpp

cpp
#include "Hospital.h"

int main(void)
{

 
 Hospital test;

 try
 {
  test.Simulate("input.txt","output.txt");
 }
 catch(char* e)
 {
  cout << "Error: " << e << endl;
 }
 
 return 0;
}

Heap.h

cpp
#ifndef HEAP_H
#define HEAP_H

template <typename T>
class Heap
{
protected:
 T* Container;
 int top;
 int max;

public:
 Heap(int Capacity)
 {
  top = 1;
  max = Capacity;
  Container = new T[max];
 }
 bool is_Empty() { return top==1; }
 bool is_Full() { return top==max; }

 bool Push(T& item);
 T* PopMax();

 void Bleeding(int x); // 응급실 환자들의 출혈량 추가
};

template <typename T>
void Heap<T>::Bleeding(int x)
{

 for(int t=1;t<top;t++)
 {
  Container[t].bleeding += x;
 }

}
template <typename T>
bool Heap<T>::Push(T& item)
{
 if( is_Full() )
  return false;

 int pos = top;
 int parent_pos;
 top++;

 Container[pos] = item;


 while( pos > 1 )
 {
  parent_pos = pos/2;
  // up-heap bubbling
  if( Container[pos] > Container[parent_pos] ) 
  {
   Container[parent_pos].swap(&Container[pos]);
  }
  else
   break;
  
  pos = parent_pos;
 }

 return true;
}

template<typename T>
T* Heap<T>::PopMax()
{
 int parent_pos;
 if(is_Empty())
  return NULL;

 T* pop = new T();

 *pop = Container[1];

 int pos = 1;
 int child_pos;

 while( pos < top )
 {
  // down-heap bubbling
  if( pos*2+1 < top )
  {
   if( Container[pos*2] > Container[pos*2+1] ) 
    child_pos = pos*2;
   else
    child_pos = pos*2+1;
  }
  else if( pos*2 < top )
   child_pos = pos*2;
  else
   break;

  if( Container[pos] > Container[child_pos] ) 
   Container[pos].swap(&Container[child_pos]);

  pos = child_pos;
 }
 top--;
 if( pos < top )
 {
  Container[top].swap(&Container[pos]);
 
 while(pos > 1)
  {
   parent_pos = pos/2;
   if(Container[pos] > Container[parent_pos])
    Container[parent_pos].swap(&Container[pos]);
   else
    break;

   pos = parent_pos;
  }

 }

 return pop;
}

#endif

Queue.h

cpp
#ifndef QUEUE_H
#define QUEUE_H

template <typename T>
class Queue
{
private:
 int head,tail,capacity;
 T* data;
public:
 Queue(int Capacity);
 ~Queue();
 
 T pop();
 bool push(T& Data);

 bool isEmpty();
};

template <typename T>
Queue<T>::Queue(int Capacity) 
{ 
 head = tail = -1;
 capacity = Capacity; 
 data = new T[capacity];
}

template <typename T>
Queue<T>::~Queue() 
{
 delete[] data;
}

template <typename T>
bool Queue<T>::isEmpty()
{
 return head==tail;
}

template <typename T>
bool Queue<T>::push(T& Data)
{

 tail = (tail + 1) % capacity;
 data[tail] = Data;

 return true;

}

template <typename T>
T Queue<T>::pop()
{
 head = (head + 1) % capacity;

 return data[head];
}

#endif

Hospital.h

cpp
#ifndef HOSPITAL_H
#define HOSPITAL_H

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>
#include "Queue.h"
#include "Heap.h"

using namespace std;

class Patient // 환자 클래스
{
public:
 int id; // ID; 1부터 시작함; 작을수록 먼저 온 환자
 bool is_emergency; // true:응급환자; false:일반환자;
 int bleeding;// 출혈량; 일반환자는 0
 int in_time;// 진료실이나 응급실에 입실하였을 때 시간

 // operator overloading!!
 // 대입 연산자
 Patient& operator=(const Patient& rhs) 
 {
  if(this == &rhs)
   return *this;

  id = rhs.id;
  is_emergency = rhs.is_emergency;
  bleeding = rhs.bleeding;
  in_time = rhs.in_time;

  return *this;
 }


 // 비교 연산자
 bool operator < (const Patient& target)
 {
  //출혈량이 같으면 먼저 온 사람부터
  return (this->bleeding == target.bleeding) ? this->id > target.id : this->bleeding < target.bleeding;
 }

 bool operator > (const Patient& target)
 {
  //출혈량이 같으면 먼저 온 사람부터
  return (this->bleeding == target.bleeding) ? this->id < target.id : this->bleeding > target.bleeding;
 }
 //end

 void swap(Patient* target)
 {
  Patient temp;
  temp = *target;
  *target = *this;
  *this = temp;
 }

};

class Room // 수술실,회복실 클래스
{
public:
 int id;// 환자ID
 bool is_emergency; // 응급/일반 환자
 int remain_time;// 퇴실 가능까지 남은 시간
 int bleeding;// 환자의 출혈량
};

class Hospital
{
private:
 // medical institution
 Queue<Patient>* Consultation;// 진료실
 Heap<Patient>* Emergency;// 응급실 (max heap)
 Room* Recovery;// 회복실
 Room* Operator;// 수술실
 Queue<Patient>* Mortuary;// 영안실
 Queue<Patient>* Leave;//퇴원한 환자 저장
 // end

 // the time
 int now_time;//현재시간변수
 // I/O
 struct input { // 입력 파일의 정보를 저장하는 구조체
  int running_time;//총 단위 시간
  int emergency_operation_time;//응급 환자의 수술 시간
  int normal_recovery_time;//응급 환자의 회복 시간
  int emergency_recovery_time;//일반 환자의 회복시간
  int bleeding_max;// 응급 환자의 최대 출혈량 (max)
  int bleeding_min;// 응급 환자의 최소 출혈량 (min)
  int bleeding_per_time;//응급 환자의 단위 시간 당 출혈량
  int normal_per_time;//단위 시간 당 일반 환자의 발생 확률 (percent)
  int emergency_per_time;//단위 시간 당 응급 환자의 발생 확률 (percent)
 } in;

 struct output { // 출력 파일의 정보를 저장하는 구조체
  int total_patient_num;//병원에 온 환자의 총 수
  int leave_normal_patient_num;//병원에서 퇴원한 일반 환자의 수
  int leave_emergency_patient_num;//병원에서 퇴원한 응급 환자의 수
  int dead_num;// 과다출혈로 사망한 환자의 수
  int consultation_room_time_average;//진료실 환자의 진료실 평균 대기 시간
  int emergency_room_time_average;//진료실에 남아 있는 일반 환자의 수
  int remain_normal_patient_num;//응급실에 남아 있는 응급 환자의 수
  int remain_emergency_patient_num;//응급실에서 수술중인 응급 환자의 존재 여부
  int remain_operation_patient;//수실실에서 수술중인 응급 환자의 존재 여부
  int remain_recovery_patient;//회복실에서 회복중인 환자(응급=2/일반=1)의 존재 여부
 } out;
 // end

 void Init() // 변수들의 초기화
 {
  // OUTPUT initailize
  struct output Out = {0,0,0,0,0,0,0,0,0,0};
  out = Out; // 출력 구조체 초기화
 
  // 시작 시간을 0으로 설정
  now_time = 0;

  // random seed initialize
  srand((unsigned int)time(NULL));

  // institution initialize
  Consultation = new Queue<Patient>(in.running_time);
  Emergency = new Heap<Patient>(in.running_time);
  Recovery = new Room;
  Operator = new Room;
  Mortuary = new Queue<Patient>(in.running_time);
  Leave = new Queue<Patient>(in.running_time * 2);

  // 회복실,수술실 비우기
  Recovery->id = 0;
  Recovery->remain_time = 0;
  Operator->id = 0;
  Operator->remain_time = 0;
 }

public:
 //Hospital();
 //~Hospital();

 void is_integrity(); //무결성 검사
 void Simulate(char* str1,char* str2); // 시뮬레이션

 void NewPatient(); // 단위시간당 환자 발생 함수
 void RoomCheck(); // 회복실,수술실 관리 함수
 void DeadCheck(); // 응급실 사망자 관리 함수

};
#endif

Hospital.cpp

cpp
#include "Hospital.h"
void Hospital::NewPatient() // 환자발생
{
 int lotto1,lotto2;
 Patient* patient1;
 Patient* patient2;

 // 0부터 99까지의 임의의 정수를 발생
 lotto1 = rand()%100;
 lotto2 = rand()%100;

 // 일반 환자 발생
 if(lotto1 < in.normal_per_time) 
 {
  out.total_patient_num++;
  patient1 = new Patient();
  patient1->id = out.total_patient_num;
  patient1->is_emergency = false;
  patient1->bleeding = 0;// 일반환자의 출혈량 0
  patient1->in_time = now_time;

  cout << patient1->id << "번 환자, 진료실에 입실" << endl;

  if(!Consultation->push(*patient1))
   throw "void Hospital::NewPatient() [patient1]";

 }

 // 응급 환자 발생
 if(lotto2 < in.emergency_per_time)
 {
  out.total_patient_num++;
  patient2 = new Patient();
  patient2->id = out.total_patient_num;
  patient2->is_emergency = true;
  patient2->bleeding = rand()%(in.bleeding_max-in.bleeding_min+1) + in.bleeding_min;
  patient2->in_time = now_time;

  cout << patient2->id << "번 응급 환자, 응급실에 입실 (출혈량:" << patient2->bleeding << ")" << endl;
  
  if(!Emergency->Push(*patient2))
   throw "void Hospital::NewPatient() [patient2]";

 }

}

void Hospital::RoomCheck() // 회복실,수술실 관리
{
  Patient temp; // 임시 변수
 
  
  // 환자의 회복이 끝났을 때
  if((Recovery->remain_time == 0)&&(Recovery->id != 0)) 
  {
   temp.id = Recovery->id;
   temp.is_emergency = Recovery->is_emergency;
   temp.bleeding = Recovery->bleeding;
   temp.in_time = 0;
   
   Leave->push(temp); // 퇴원

   cout << temp.id << "번 " << ((temp.is_emergency)?"응급 ":"") <<"환자가 퇴원하였다." << endl;

   // 퇴원한 환자수 계산
   if(Recovery->is_emergency)
    out.leave_emergency_patient_num++;
   else
    out.leave_normal_patient_num++;

   // 회복실을 비운다
   Recovery->id = 0;
   Recovery->remain_time = 0;
  }

  // 회복실이 비었을 때
  if((Recovery->remain_time == 0)&&(Recovery->id == 0)) 
  {
   if((Operator->remain_time == 0)&&(Operator->id != 0)) // 수술실의 수술이 끝나면
   {
    // 회복실에 환자를 입실시킨다 
    Recovery->id = Operator->id;
    Recovery->is_emergency = Operator->is_emergency;
    Recovery->remain_time = in.emergency_recovery_time;
    Recovery->bleeding = Operator->bleeding;
    
    cout << Recovery->id << "번 " << ((Recovery->is_emergency)?"응급 ":"") <<"환자가 회복실에 입실하였다." << endl;
    
    // 수술실을 비운다
    Operator->id = 0;
    Operator->remain_time = 0;
   }
   else if(Operator->remain_time != 0) // 수술이 끝나지 않았으면
   {
    if(!Consultation->isEmpty()) // 진료실이 환자가 존재하면
    {
     // 회복실에 환자를 입실시킨다
     temp = Consultation->pop();
     Recovery->id = temp.id;
     Recovery->is_emergency = temp.is_emergency;
     Recovery->remain_time = in.normal_recovery_time;
     Recovery->bleeding = temp.bleeding;
     // 대기시간 변수에 대기시간을 더함
     out.consultation_room_time_average += (now_time - temp.in_time);
 
     cout << Recovery->id << "번 " << ((Recovery->is_emergency)?"응급 ":"") <<"환자가 회복실에 입실하였다." << endl;

    }
   }

   if((Operator->remain_time == 0)&&(Operator->id == 0)) // 수술실이 비었으면
   {
    if(!Emergency->is_Empty()) // 응급실에 환자가 존재하면
    {
     // 수술실에 환자를 입실시킨다
     temp = *Emergency->PopMax();
     Operator->id = temp.id;
     Operator->is_emergency = temp.is_emergency;
     Operator->remain_time = in.emergency_operation_time;
     Operator->bleeding = temp.bleeding;
     out.emergency_room_time_average += (now_time - temp.in_time);

     cout << Operator->id << "번 응급 환자가 수술실에 입실하였다. (출혈량:"<< Operator->bleeding <<")" << endl;

    }
   }
  }

  if(Recovery->remain_time != 0)
  {
   cout << "회복실: " << Recovery->id << "번 환자 회복까지 " << Recovery->remain_time << "턴 남았습니다" << endl;
   Recovery->remain_time--;
  }
  if(Operator->remain_time != 0)
  {
   cout << "수술실: " << Operator->id << "번 환자 수술완료까지 " << Operator->remain_time << "턴 남았습니다" << endl;
   Operator->remain_time--;
  }
  else
  {
   if(Operator->id != 0)
    cout << "수술실: " << Operator->id << "번 환자 수술완료, 회복실 입실 대기중입니다" << endl;
  }

}

void Hospital::DeadCheck()
{
 Patient* s;

 Emergency->Bleeding(in.bleeding_per_time);//단위시간당 응급실 환자의 출혈량 증가
  
 while(!Emergency->is_Empty()) // 응급실이 비어있지 않으면
 {
  s = Emergency->PopMax(); // max heap의 최상위 데이터
  
  if(s->bleeding <= in.bleeding_max) // 최대 출혈량보다 작으면 루프를 멈춤
  {
   Emergency->Push(*s); // 다시 넣는다
   break;
  }
  
  // 최대 출혈량을 초과하는 환자 존재시 영안실로 이동

  cout << s->id << "번 응급 환자, 사망하여 영안실로 이동합니다 (출혈량:" << s->bleeding << ")" << endl;

  Mortuary->push(*s);
  out.dead_num++;
 }

}

void Hospital::Simulate(char* str1,char* str2)
{

 // file read
 
 int* t;
 int i;
 char c,e;

 ifstream file1;
 file1.open(str1);
 
 i = 0;
 //explit type conversion!!
 t = (int*)(&in);
 // input data to struct 'input'
 while(!file1.eof())
 {
  file1 >> *(t+i);
  i++;
 }
 //end
 file1.close();

 // file read end


 cout << "HW#2 Hospital Simulation" << endl
  << "1. start with history" << endl
  << "2. start without history" << endl
  << "0. exit" << endl
  << ">>";
 cin.get(c);
 cin.get();
 cout << endl;

 if(c == '0')
  return;

 // I/O initialize
 Init();

 // start simulate
 while(!(now_time == in.running_time))
 {
  cout << now_time+1 << "턴-" << endl;


  DeadCheck();

  NewPatient();
  
  RoomCheck();

  
  now_time++;
  
  cout << endl;


  // for test..
  if(c == '1')
   cin.get(e);
  else
   e = NULL;

  // exit
  if(e == '0')
   return;

 }


 is_integrity();

 cout << "Press any key to write output file..";
 cin.get();

 // file write
 ofstream file2;
 file2.open(str2);
 
 i = 0;
 //explit type conversion!!
 t = (int*)(&out);
 // input data to struct 'input'
 while(i<10)
 {
  file2 << *(t+i) << endl;
  i++;
 }
 //end
 file2.close();

 // file write end

 //return true;
}

void Hospital::is_integrity()
{
 Patient temp;
 int total=0,normal=0,emergency=0,dead=0,wait_c=0,wait_e=0,o,r;

 cout << "무결성 검사-" << endl;
 cout << "퇴원한 환자: ";
 while(!Leave->isEmpty())
 {
  temp = Leave->pop();
  total++;

  if(temp.is_emergency)
   emergency++;
  else
   normal++;

  cout << temp.id << " "; 
 }
 cout << "(총 " << total << "명)" << endl;

 cout << "사망한 환자: ";
 while(!Mortuary->isEmpty())
 {
  temp = Mortuary->pop();
  total++;
  dead++;

  cout << temp.id << " ";
 }
 cout << "(총 " << dead << "명)" << endl;


 cout << "진료받지 못한 환자: ";
 while(!Consultation->isEmpty())
 {
  temp = Consultation->pop();
  total++;
  wait_c++;

  cout << temp.id << " ";
 }
 cout << "(총 " << wait_c << "명)" << endl;

 
 cout << "치료받지 못한 응급환자: ";
 while(!Emergency->is_Empty())
 {
  temp = *Emergency->PopMax();
  total++;
  wait_e++;
  
  cout << temp.id << " ";
 }
 cout << "(총 " << wait_e << "명)" << endl;

 
 cout << "수술 중인 응급환자: ";
 if(Operator->id)
 {
  total++;
  o = 1;
  
  cout << Operator->id << " ";
 }
 else
  o = 0;

 cout << "(총 " << o << "명)" << endl;


 cout << "치료 중인 환자: ";
 if(Recovery->id)
 {
  total++;
  if(Recovery->is_emergency)
   r = 2;
  else 
   r = 1;
  
  cout << Recovery->id << " ";
 }
 else
 {
  r = 0;
 }
 cout << "(총 " << ((r>0)?"1":"0") << "명"<< ((r==2)?", 응급":"") << ")" << endl;

 cout << "총 환자 수: " << total << "명" << endl;

 if(out.total_patient_num != total) throw "1";
 if(out.leave_normal_patient_num != normal) throw "2";
 if(out.leave_emergency_patient_num != emergency) throw "3";
 if(out.dead_num != dead) throw "4";

 out.remain_normal_patient_num = wait_c;
 out.remain_emergency_patient_num = wait_e;
 out.remain_operation_patient = o;
 out.remain_recovery_patient = r;

 // 평균 대기시간은 반올림
 out.consultation_room_time_average = (int)(double)((out.consultation_room_time_average/(normal+((r==1)?1:0))) + 0.5);
 out.emergency_room_time_average = (int)(double)((out.emergency_room_time_average/(emergency+o+((r==2)?1:0))) + 0.5);

}