SW Expert Academy - 2383. 점심 식사시간

문제링크

• 점심 식사시간

문제설명

• 링크 참고

문제접근

• 사람들이 이용할 계단을 선택할 수 있는 모든 경우의 수를 구하고, 각 경우의 수에 대해서 모든 사람들이 계단을 내려가 이동이 완료되는 시간을 계산하고 최솟값을 구한다.
  • 모든 사람들이 한 계단만을 이용할 수도 있음. 즉, 이용하지 않는 계단이 있을수도 있음
• 계단을 내려가는 함수 작성이 가장 중요한 부분이었던걸로 생각됨
  • 계단 1, 2 구분없이 하나의 함수에서 동작할 수 있도록 구현해야 함
• 계단 입구에 도착하는 시간 기준으로 오름차순 정렬함
• 계단을 내려갈 때 최대 3명만 동시에 계단을 내려갈 수 있음에 유의
  • 동일한 시간에 도착한 사람이 4명이어도 임의로 3명만 내려가고 한명은 대기해야함
  • 대기하는 경우 내가 도착한 시간이 아니라 계단을 가장 먼저 다 내려간 사람의 시간을 기준으로 내려가야하는 것에 유의
  • 큐 자료구조로 계단을 내려가는 것이 완료된 시간을 담음

구현

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <memory.h>

#define EXIT_0 0
#define EXIT_1 1
#define MIN_STEP 2
#define PERSON 1
#define MAX_STEP_USER 3
#define MAX_PEOPLE 10
using namespace std;

typedef struct _step_info {
	int xpos;
	int ypos;
	int downTime;
} STEP;

int N;
vector<STEP> exitInfo;
vector<pair<int, int>> people;
vector<int> step_1_user;
vector<int> step_2_user;
bool visited[MAX_PEOPLE];

void init()
{
	people.clear();
	exitInfo.clear();
}

void input()
{
	init();
	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			int val;
			cin >> val;
			if (val >= MIN_STEP) exitInfo.push_back({ r,c,val });
			else if (val == PERSON) people.push_back(make_pair(r, c));
		}
	}
}

int getAllStepDownTime(vector<int>& moveTime, STEP& stepInfo)
{
	queue<int> q;
	for (int i = 0; i < moveTime.size(); i++) {
		if (q.empty()) q.push(moveTime[i] + stepInfo.downTime + 1);
		else {
			while (q.front() <= moveTime[i]) {
				q.pop();
				if (q.empty()) break;
			}
			if (q.size() >= MAX_STEP_USER) {
				q.push(q.front() + stepInfo.downTime); // 1번째 사람 내려간 이후
				q.pop();
			}
			else {
				q.push(moveTime[i] + stepInfo.downTime + 1);
			}
		}
	}

	int ret = 0;
	while (!q.empty()) {
		ret = q.front();
		q.pop();
	}
	return ret;
}

int getTotalProcessTime(vector<int> stepUser, STEP stepInfo)
{
	vector<int> moveTime;
	for (auto ele : stepUser) {
		int pr = people[ele].first;
		int pc = people[ele].second;
		moveTime.push_back(abs(pr - stepInfo.xpos) + abs(pc - stepInfo.ypos));
	}
	sort(moveTime.begin(), moveTime.end());
	return getAllStepDownTime(moveTime, stepInfo);
}

void setStep2user()
{
	step_2_user.clear();
	bool isStep1[MAX_PEOPLE];
	memset(isStep1, false, sizeof(isStep1));
	for (int i = 0; i < step_1_user.size(); i++) {
		isStep1[step_1_user[i]] = true;
	}

	for (int i = 0; i < people.size(); i++) {
		if (isStep1[i]==false) step_2_user.push_back(i);
	}
}

int dfs(int v, int cnt)
{
	if (step_1_user.size() == cnt) {
		setStep2user();
		return max(getTotalProcessTime(step_1_user, exitInfo[EXIT_0]), getTotalProcessTime(step_2_user, exitInfo[EXIT_1]));
	}

	int ret = INT_MAX;
	for (int i = v; i < people.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		step_1_user.push_back(i);
		ret = min(ret, dfs(i + 1, cnt));
		visited[i] = false;
		step_1_user.pop_back();
	}

	return ret;
}

int solution()
{
	int ret = INT_MAX;
	for (int i = 0; i <= people.size(); i++) {
		ret = min(ret, dfs(0, i));
	}
	return ret;
}

void test()
{
	input();
	cout << solution() << endl;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	//freopen("input.txt", "r", stdin);
	cin >> T;
	// test();
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		cout << "#" << test_case << " " << solution() << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}