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

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

링크 : 2383. [모의 SW 역량테스트] 점심 식사시간 (로그인 필요)

N*N크기 맵에 2개의 계단, 사람들이 주어진다. 계단은 길이가 존재하고, 계단에는 최대 3명이 올라갈 수 있다.

이러 계단을 이용해서 모든 사람들이 내려갔을 때 최소시간을 구하면 된다.

여러 풀이 방법이 있겠지만, 직관적으로 생각하기 좋은 방법은 "조합 + 시뮬레이션"일 것 같다.

조합을 통해 사람들을 2개의 그룹으로 나눠 계단을 내려가는 시뮬레이션을 진행하였다.

여기서 주의 할 점은

1. 계단은 최대 3명이 이용할 수 있다.

2. 계단에 도착 후 다음 시간(초)에 계단에 진입한다.

3. 이미 대기를 하고 있으면 계단에서 사람이 빠지는 순간 계단으로 들어갈 수 있다. 

(예 : (4초)A,B,F가 계단을 이용 중, B,C가 대기 중// (5초)A,B,F가 계단을 빠져나감, (5초) B,C 계단에 진입)

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
struct pnt1 { int r, c, Group; };
struct pnt2 { int r, c, dist; };
struct pnt3 { int r, c, len; };
vector<pnt3>stair;
vector<pnt1>All;
vector<pnt2>Group1, Group2;
int N, ans = 1e9;

bool cmp(const pnt2 &a, const pnt2 &b) {
	if (a.dist < b.dist) return true;
	else return false;
}

void go() {
	queue<int>s1, s2, w1, w2;
	int idx1 = 0, idx2 = 0;
	int time1 = 1, time2 = 1;
	while (1) {
		while (!s1.empty() && s1.front() + stair[0].len <= time1)
			s1.pop();
		while (!w1.empty() && s1.size() < 3) {
			s1.push(time1);
			w1.pop();
		}
		while (idx1 < Group1.size() && Group1[idx1].dist == time1) {
			w1.push(time1);
			idx1++;
		}
		
		if (s1.empty() && w1.empty()&&idx1 >= Group1.size())break;
		time1++;
		if (time1 >= ans) return;
	}
	while (1) {
		while (!s2.empty() && s2.front() + stair[1].len <= time2)
			s2.pop();
		while (!w2.empty() && s2.size() < 3) {
			s2.push(time2);
			w2.pop();
		}
		while (idx2 < Group2.size() && Group2[idx2].dist == time2) {
			w2.push(time2);
			idx2++;
		}
		if (s2.empty() && w2.empty()&&idx2 >= Group2.size())break;
		time2++;
		if (time2 >= ans) return;
	}
	int tmp = time1 < time2 ? time2 : time1;
	ans = tmp < ans ? tmp : ans;

}

void setGroup(int idx) {
	if (idx == All.size()) {
		for (int i = 0; i < All.size(); i++) {
			int r = All[i].r;
			int c = All[i].c;
			if (All[i].Group == 0) {
				int dist = abs(All[i].r - stair[0].r) + abs(All[i].c - stair[0].c);
				Group1.push_back({ r,c, dist });
			}
			else {
				int dist = abs(All[i].r - stair[1].r) + abs(All[i].c - stair[1].c);
				Group2.push_back({ r,c,dist });
			}
		}
		sort(Group1.begin(), Group1.end(), cmp);
		sort(Group2.begin(), Group2.end(), cmp);
		go();
		Group1.clear();
		Group2.clear();
		return;
	}
	All[idx].Group = 1;
	setGroup(idx + 1);
	All[idx].Group = 0;
	setGroup(idx + 1);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		for (int r = 1; r <= N; r++) {
			for (int c = 1; c <= N; c++) {
				int in;
				cin >> in;
				if (in == 0)continue;
				else if (in == 1)
					All.push_back({ r,c,0 });
				else
					stair.push_back({ r,c,in });
			}
		}
		setGroup(0);
		cout << '#' << tc << ' ' << ans << '\n';
		All.clear();
		stair.clear();
		ans = 1e9;
	}
	return 0;
}