[모의 SW 역량테스트] 점심 식사시간- 2383

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

SW Expert Academy

코드 : 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <map>
#include <limits>

using namespace std;

class Person
{
public:
	int key; //배열 인덱스
	int x, y; // 사람좌표
	int aStairs, bStairs; // 각각의 계단입구까지 걸리는 시간
	int enter; // 선택된 계단 입구
	int lowCount; // 현재 내려가는 시간
	bool arrivdeStairs; // 계단입구까지 도착한 상태
	bool finish; // 최종 도착여부
};

int N;
int minTime = INT32_MAX;
int num[10][10] = { 0 };
int stairs[2][2] = { 0 };
Person person[10];
int personCount = 0;

vector<Person> realAV, tempAV;
vector<Person> realBV, tempBV;

void SearchPerson()
{
	personCount = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (num[i][j] == 1)
			{
				person[personCount].key = personCount;
				person[personCount].x = i;
				person[personCount].y = j;
				person[personCount].aStairs = abs(i - stairs[0][0]) + abs(j - stairs[0][1]);
				person[personCount].bStairs = abs(i - stairs[1][0]) + abs(j - stairs[1][1]);
				person[personCount].lowCount = 0;
				person[personCount].arrivdeStairs = false;
				person[personCount].finish = false;
				personCount++;
			}
		}
	}
}

void CalcStairsPersonA()
{
	int size = realAV.size();
	for (int i = 0; i < size; i++)
	{
		realAV[i].lowCount -= 1;
		if (realAV[i].lowCount < 0)
		{
			realAV[i].finish = true;
			person[realAV[i].key].finish = true;
		}
	}
	int index = -1;
	for (int i = 0; i < size; i++)
	{
		if (realAV[i].finish)
		{
			index = i;
		}
	}
	if (index != -1)
		realAV.erase(realAV.begin(), realAV.begin() + (index + 1));

	int addCount = 3 - realAV.size();
	addCount = addCount > tempAV.size() ? tempAV.size() : addCount;
	for (int i = 0; i < addCount; i++)
	{
		tempAV[i].lowCount -= 1;
		realAV.push_back(tempAV[i]);
	}
	if (addCount > 0)
	{
		tempAV.erase(tempAV.begin(), tempAV.begin() + addCount);
	}
}

void CalcStairsPersonB()
{
	//계단 내려가는 사람 처리
	int size = realBV.size();
	for (int i = 0; i < size; i++)
	{
		realBV[i].lowCount -= 1;
		if (realBV[i].lowCount < 0) // 다 내려왔으면
		{
			realBV[i].finish = true;
			person[realBV[i].key].finish = true;
		}
	}
	int index = -1;
	for (int i = 0; i < size; i++)
	{
		if (realBV[i].finish)
		{
			index = i;
		}
	}
	if (index != -1)
		realBV.erase(realBV.begin(), realBV.begin() + (index + 1));

	//대기하는 사람 처리
	int addCount = 3 - realBV.size();
	//실제 추가해야될 인원 구하기
	addCount = addCount > tempBV.size() ? tempBV.size() : addCount;
	for (int i = 0; i < addCount; i++)
	{
		tempBV[i].lowCount -= 1;
		realBV.push_back(tempBV[i]);
	}
	if (addCount > 0)
	{
		tempBV.erase(tempBV.begin(), tempBV.begin() + addCount);
	}
}

int Calc()
{

	int time = 1;
	while (true)
	{
		CalcStairsPersonA();
		CalcStairsPersonB();

		for (int i = 0; i < personCount; i++)
		{
			if (person[i].arrivdeStairs)
				continue;
			if (person[i].enter == 0)
			{
				if (time == person[i].aStairs)
				{
					person[i].arrivdeStairs = true;
					tempAV.push_back(person[i]);
				}
			}
			else
			{
				if (time == person[i].bStairs)
				{
					person[i].arrivdeStairs = true;
					tempBV.push_back(person[i]);
				}
			}
		}
		bool check = true;
		for (int i = 0; i < personCount; i++)
		{
			if (person[i].finish == false)
			{
				check = false;
				break;
			}
		}
		if (check)
		{
			realAV.clear();
			realBV.clear();
			tempAV.clear();
			tempBV.clear();
			return time;
		}
		time++;
	}
	return time;
}

void SelectStairs()
{
	int arr[10] = { 0 };
	int i = 0;
	//사람들이 계단을 선택할 수 있는 모든 경우의 수
	while (i <= personCount)
	{
		do
		{
			for (int c = 0; c < personCount; c++)
			{
				person[c].enter = arr[c]; // 0이면 A계단, 1이면 B계단
				int y = stairs[arr[c]][0];
				int x = stairs[arr[c]][1];
				person[c].lowCount = num[y][x]; // 계단 내려가는 시간 저장
				person[c].finish = false;
				person[c].arrivdeStairs = false;
			}
			int time = Calc();
			if (minTime > time)
			{
				minTime = time;
			}
		} while (prev_permutation(arr, &arr[personCount]));
		arr[i++] = 1;
	}
}

void Solution()
{
	SearchPerson();
	SelectStairs();
}

int main()
{
	int count = 0;
	cin >> count;

	int c = 1;
	while (c <= count)
	{
		minTime = INT32_MAX;
		cin >> N;
		int r = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> num[i][j];
				//계단 저장
				if (num[i][j] != 0 && num[i][j] != 1)
				{
					stairs[r][0] = i;
					stairs[r++][1] = j;
				}
			}
		}
		Solution();
		cout << "#" << c << " " << minTime << "\n";
		c++;
	}

	return 0;
}

 

생각보다 시간이 좀 많이(6시간) 걸린 문제이다...

나름 재미있었는데 시간은 오래걸렸지만 다행이도 50개 테스트 케이스를 한번에 통과해서 기분이 째짐~!

이 문제를 처음 접근할때 계단을 머릿속으로는 2개라고 생각하면서 풀었는데 왜 실제 로직설계할땐 계단을 한개로 생각해서 접근을 했다... (ㅁㄹㅈㄷㄹㅈㄹ)

거의 구현을 마치고 다시 리펙토링을 진행해보니 vector를 사용하여 추가빼고하는 작업을 queue를 사용하면 더 간단해질 것 같다. 추가빼는 작업으로인해 많이 지져분해졌는데... 

왜 vector로 진행했을까 생각해보니 처음 접근할때 잘못 생각한 계단을 한개로 생각했을때가 문제였다. 계단을 한개로 생각하면 A, B계단의 내려가는 계단 수가 각각 다르므로 선입선출을 사용할 수 없었기 때문이였다....

우선 접근할때 크게 2개로 나누어서 생각했다. 

1. 사람들이 계단을 선택할 수 있는 모든 경우의 수 처리
2. 사람들이 모두다 내려가는 시간계산

1번은 next_permutaion을 사용하여 금방 해결하였다.

2번이 이 문제의 핵심인데.. 고민한 부분들을 좀 적어보겠다.

처음엔 시간이 순증 함에 따라 어떻게 처리해야 될지 고민이었다.

무슨말이냐 하면 입구까지 도착한 사람들은 1분 기다리고 내려가기 시작해야되는데 이를 어떻게 처리할지 고민을 좀 했다. 처음엔 단순하게 '입구까지 도착한 사람들 추출 -> 입구도착한 사람들은 계단내려가도록 처리' 루프처리를 하려고했는데 이렇게 되면 1분 기다리는 처리가 힘들었다. 그래서 이 순서를 바꿔서 입구도착한 사람들 먼저 처리하고 그다음에 입구도착한 사람들 추출하는 방식으로 처리하자고 결론지었다.

이부분은 이렇게 해결했고 나머진 vector를 사용해서 넣고 빼고 하는 작업이라 복잡하기만 하다... 

간략하게 A계단만 정리하자면 'A계단 도착vector를 탐색하여 내려가도록 처리(이때 다 내려간경우는 vector에서 제거) -> 도착Vector는 3명만 들어갈 수 있음에 따라 tempVector에서 빼서 도착vector에 넣을 수 있을만큼 넣음 -> 사람 전체탐색해서 입구도착시간이 된 사람들은 tempVector에 추가

B계단도 마찬가지로 처리를 하였다. 

P.S 그러고보니 모든 경우의 수를 구할때 next_permutation 함수를 사용하였는데 재귀함수를 사용해도 되겠다. 

나중에 vector -> queue, next_permutation -> 재귀함수 로 변경하여 다시한번 문제를 풀어봐야 겠다. 위 코드는.. 너무 쪽팔린다..ㅜㅜ 그래서 접어둠.. ㅋㅋㅋ

---

다시 풀어보았는데... 뭔가 생각대로 잘.....ㅜㅜ

코드 : 

#include <iostream>
#include <limits>
#include <math.h>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

class Person2
{
public:
	int x, y; // 현재 위치
	bool aSelect; // A계단 선택 유무
	int aTime; // A 입구까지 걸리는 시간
	int bTime; // B 입구까지 걸리는 시간
	bool mArride; // 계단 입구까지 도착유무
	int mArrideTime; // 계단 입구에서 내려가는 시작시간
	bool finish; // 완전 종료
};

int num[10][10] = { 0 };
int minTime = INT32_MAX;
Person2 person[10];
int stairs[2] = { 0 }; // A, B 계단 갯수 저장
std::pair<int, int> stairsPosition[2]; // 가로, 세로 // A, B
queue<Person2> aRealArray; // A 내려가는 사람들
queue<Person2> bRealArray; // B 내려가는 사람들
queue<Person2> aTempArray; // 임시 대기 사람들
queue<Person2> bTempArray; // 임시 대기 사람들

int Calculate(int personCount)
{
	int time = 1;
	int checkCount = 0;
	while (true)
	{
		int queCount = 0;
		// 내려가는 사람 처리
		if (aRealArray.empty() == false)
		{
			int size = aRealArray.size();
			for (int i = 0; i < size; i++)
			{
				if (time - aRealArray.front().mArrideTime > stairs[0])
				{
					aRealArray.pop();
					checkCount++;
				}
			}
		}
		if (bRealArray.empty() == false)
		{
			int size = bRealArray.size();
			for (int i = 0; i < size; i++)
			{
				if (time - bRealArray.front().mArrideTime > stairs[1])
				{
					bRealArray.pop();
					checkCount++;
				}
			}
		}
		//계단입구에 도착했을 때 처리
		for (int i = 0; i < personCount; i++)
		{
			if (person[i].aSelect)
			{
				if (time == person[i].aTime)
				{
					person[i].mArride = true;
					if (aRealArray.size() != 3)
					{
						Person2 temp = person[i];
						temp.mArrideTime = time;
						aRealArray.push(temp);
					}
					else
					{
						aTempArray.push(person[i]);
					}
				}
			}
			else
			{
				if (time == person[i].bTime)
				{
					person[i].mArride = true;

					if (bRealArray.size() != 3)
					{
						Person2 temp = person[i];
						temp.mArrideTime = time;
						bRealArray.push(temp);
					}
					else
					{
						bTempArray.push(person[i]);
					}
				}
			}
		}
		//먼저 내려간 애들로 인해 대기중인 애들이 있다면 추가
		while (aRealArray.size() != 3 && aTempArray.empty() == false)
		{
			aTempArray.front().mArrideTime = time - 1;
			aRealArray.push(aTempArray.front());
			aTempArray.pop();
		}
		while (bRealArray.size() != 3 && bTempArray.empty() == false)
		{
			bTempArray.front().mArrideTime = time - 1;
			bRealArray.push(bTempArray.front());
			bTempArray.pop();
		}
		if (checkCount == personCount)
		{
			return time;
		}
		time++;
	}
}

// 사람 인덱스, 총 사람 수, A계단 선택유무
void solution(int index, int personCount, bool aStairs)
{
	bool check[10] = { false };
	for (int c = -1; c < personCount; c++)
	{
		if (c != -1)
		{
			check[c] = true;
		}
		do
		{
			for (int i = 0; i < personCount; i++)
			{
				//cout << check[i];
				if (check[i] == false)
				{
					person[i].aSelect = true;
					person[i].aTime = abs(person[i].y - stairsPosition[0].first)
						+ abs(person[i].x - stairsPosition[0].second);
				}
				else
				{
					person[i].aSelect = false;
					person[i].bTime = abs(person[i].y - stairsPosition[1].first)
						+ abs(person[i].x - stairsPosition[1].second);
				}
			}
			int time = Calculate(personCount);
			if (minTime > time)
			{
				minTime = time;
			}
			//cout << "\t" << minTime << endl;
		} while (prev_permutation(check, &check[personCount]));
	}

}

int main()
{
	int count;
	cin >> count;
	int c = 1;
	while (c <= count)
	{
		minTime = INT32_MAX;
		int N;
		cin >> N;

		int personCount = 0;
		int stairIndex = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> num[i][j];
				if (num[i][j] == 1)
				{
					person[personCount].x = j;
					person[personCount].y = i;
					person[personCount].mArride = false;
					person[personCount].finish = false;
					personCount++;
				}
				if (num[i][j] != 1 && num[i][j] != 0)
				{
					stairs[stairIndex] = num[i][j]; // 계단 내리막 값 저장
					stairsPosition[stairIndex].first = i; // 가로
					stairsPosition[stairIndex++].second = j;// 세로
				}
			}
		}
		solution(0, personCount, true);
		cout << "#" << c << " " << minTime << "\n";
		c++;
	}
	return 0;
}

일단 재귀로 풀려고 계속 시도를 했는데 생각보다 처리가 까다로웠다. 그래서 다시 라이브러리를 사용하였고, 큐를 사용하긴 했는데 뭔가 좀 복잡해 보인다. 좀더 잘 풀수 있을꺼 같은데.. 시간은 처음보단 줄었지만.. 아직도 이거 한문제도 못풀고 끝날듯;;; 다음에 또 풀어봐야겠다.