[SWEA] #2383 _ 점심 식사시간

[점심 식사시간] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

사람이 1번 계단을 이용하는 경우와 2번 계단을 이용하는 경우 두 가지의 경우를 고려할 수 있다.

이는 chk 배열을 이용하여 구현하였다.

 

s_1과 s_2는 1번 계단과 2번 계단을 이용하는 사람을 저장하는 벡터이고,

val은 계단과 사람의 거리이다.

(거리가 짧을 수록 먼저 도착하기 때문)

 

계단을 이용할 수 있는 모든 방법의 시간을 계산하여 최소 시간을 구하였다.

 

[ 소스 코드 ]

#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAX 10

using namespace std;

int N, map[MAX][MAX], minVal, chk[10];
vector<pair<int, int> > person, stair;

void init();
void solve(int idx);
int getTime();
int main() {
	int test_case;
	scanf("%d", &test_case);
	for (int i = 1; i <= test_case; i++) {
		scanf("%d", &N);

		init();

		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				scanf("%d", &map[j][k]);
				if (map[j][k] == 1) person.push_back(make_pair(j, k));
				else if (map[j][k] >= 2) stair.push_back(make_pair(j, k));
			}
		}
		solve(0);

		printf("#%d %d\n", i, minVal);
	}

	return 0;
}

void init() {
	for (int i = 0; i < N; i++) chk[i] = 0;
	minVal = 9999999;
	person.clear();
	stair.clear();
}

void solve(int idx) {
	if (idx >= person.size()) {
		minVal = min(minVal, getTime());
		return;
	}
	chk[idx] = 1;
	solve(idx + 1);
	chk[idx] = 2;
	solve(idx + 1);
}

int getTime() {
	vector<int> s_1, s_2;
	queue<int> e_1, e_2, tmp_q;
	int val, tmp, time = 0;

	for (int i = 0; i < person.size(); i++) { // 각 계단에 사람 배치
		if (chk[i] == 1) {
			val = abs(stair[0].first - person[i].first) + abs(stair[0].second - person[i].second);
			s_1.push_back(val);
		}
		else {
			val = abs(stair[1].first - person[i].first) + abs(stair[1].second - person[i].second);
			s_2.push_back(val);
		}
	}
	
	sort(s_1.begin(), s_1.end());
	sort(s_2.begin(), s_2.end());

	while (1) {
		time++;
		if (s_1.size() == 0 && s_2.size() == 0 && e_1.empty() && e_2.empty()) break;

		int s = s_1.size();
		for (int i = 0; i < s; i++) {
			tmp = s_1.front();
			s_1.erase(s_1.begin());
			if (tmp <= time) e_1.push(map[stair[0].first][stair[0].second] + 1);
			else s_1.push_back(tmp);
		}

		s = s_2.size();
		for (int i = 0; i < s; i++) {
			tmp = s_2.front();
			s_2.erase(s_2.begin());
			if (tmp <= time) e_2.push(map[stair[1].first][stair[1].second] + 1);
			else s_2.push_back(tmp);
		}

		// 한번에 계단을 이용할 수 있는 사람 수는 3명
		int cnt = 0;
		s = e_1.size();
		for (int i = 0; i < s; i++) {
			if (cnt < 3) tmp = e_1.front() - 1;
			else tmp = e_1.front();
			e_1.pop();

			if (tmp > 0) e_1.push(tmp);
			else cnt--;

			cnt++;
		}

		cnt = 0;
		s = e_2.size();
		for (int i = 0; i < s; i++) {
			if (cnt < 3) tmp = e_2.front() - 1;
			else tmp = e_2.front();
			e_2.pop();

			if (tmp > 0) e_2.push(tmp);
			else cnt--;

			cnt++;
		}
	}

	return time;
}