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

"개인적으로 모의SW역량 테스트 문제 중에서 가장 어렵다고 생각한 문제"

 

 알고리즘으로만 놓고 본다면 자료구조를 사용한 시뮬레이션 구현문제 정도이지만, 

설계하는 과정에서 자료구조나 구조체 변수를 정확하고 깔끔하게 설계해놓고 시작하지 않으면

시간내에 풀기도 어려울 뿐더러, 디버깅하기도 쉽지 않다.

 

[문제  설명]

 "문제 풀이에 들어가기 앞서 충분히 문제에 대한 이해를 하고 접근해야한다."

 

 사람들이 계단을 통해 아래 층으로 내려가려고 한다.

P는 사람의 위치, S는 계단의 위치를 의미한다.

 

사람(P)는 계단(S)까지 이동하여야 하며, 계단에 도착 후 계단을 내려간다.

계단까지의 이동 시간: |Py-Sy| + |Px-Sx| 은 맨해튼 거리로 계산한다.  

 

 계단을 내려가는 시간은 입구 도착 후 완전히 내려갈 때의 시간이다.

 

1) 계단 도착 후 1분 후 아래로 내려갈 수 있다.

2) 계단에 동시에 3명까지만 존재할 수 있다. 

3) 이미 3명이 올라있다면 입구에서 대기한다.

4) 계단의 길이는 K로 주어진다.

 

 

이 때  모든 사람이 계단을 내려오는 데 걸리는 최소 시간을 구하면 된다.

 

[문제 풀이] 

 1.  Greedy vs brute force(탐욕법 vs 완전탐색)

 

  

    설계를 하기전에 문제를 해결할 가장 큰 접근법을 '정확하게' 정하고 시작하는 게 정신 건강에 좋다.

   문제를 읽고 '모든 사람이 계단을 내려오는 데 걸리는 최소 시간' 이라는 조건을 보면 아마 대부분의 사람들은

   '사람들이 가장 가까운 계단을 이용하는 것이 최소시간이 걸리겠지?'라고 나름대로 규칙을 생각할 것이다.

 

예시.1 녹색이 사람, 파란색이 계단

 

 위 그림은 모든 사람이 자신과 가장 가까운 계단을 선택한 경우이다.

 

1초: 계단에 3명 도착

2초: 계단에 1명도착, 나머지 3명 내려가기 시작

5초: 3명 계단에서 나옴,1명 계단 내려가기 시작

8초: 모든 사람 계단에서 내려옴

 

모든 사람이 내려오는 데 8초가 걸린다. (물론,해당경우는 최소시간이 걸리는 경우이다.)

 

예시.2 녹색이 사람, 파란색이 계단

 하지만 위에 경우처럼 가장 가까운 계단이 매우 길어서 대기 시간이 길어진다면 

'가까운 계단을 이용하는 것이 최소시간이 걸린다'라는 규칙이 과연 유효할까?

정답은 아니다.

간단한 예를 통해 해당 규칙에 대한 반례가 발견되었기 때문에 Greedy를 적용해선 안된다.

 

'모든 사람이 2가지 계단을 모두 선택하는 경우의 수를 다 따져보는 완전탐색을 적용해야한다.' 

 

*문제 풀 때, 특히 시험장에서 절대 케이스 생성함수부터 구현하지말고,

 문제에서 주어진 고정된 케이스를 가지고 시뮬레이션하는 함수부터 구현하자. ㄹㅇ 조졋다.

 

2. 자료 구조 설계

사람들이 계단에 도착하고 '계단에 도착한 순서대로' 계단을 내려가거나 혹은 대기한다.

순.서.대.로 그렇다. 큐를 이용해볼까? 라는 생각이 강하게 든다.

 

(1) 계단 큐, 대기 큐 - 큐를 2개 이용하는 방법

 

 

 도착하는 순서대로 일단 stair큐에 저장을 하고 만약 stair큐의 크기가 3이라면 waiting 큐에 저장한다.

 

 

 

 stair 큐의 사이즈만큼 반복문을 돌면서 front를 pop해서 1씩 빼준다.

만약, front에 값이 0이 되었다면, 계단 탈출을 의미하는 out을 1 더해주고, wating의 front를 pop한 후

stair 큐에 넣어준다.

void simulation()
{
	int time = 0;
	int fin = 0;
	for (int i = 0; i < P_sz; i++)
	{
		Arrive[i] = cal_dist(P[i].y, P[i].x, S[sel[i]].y, S[sel[i]].x)+1;
	}
	queue<int> G[2], W[2];
	while (1)
	{
		if (time > ans) return;
		if (fin == P_sz) break;
		for (int i = 0; i < P_sz; i++)
		{
			if (Arrive[i] == time)
			{
				if (G[sel[i]].size() < 3) G[sel[i]].push(S[sel[i]].K);
				else W[sel[i]].push(S[sel[i]].K);
			}
		}
		for (int i = 0; i < 2; i++)
		{
			int q_sz = G[i].size();
			for (int j = 0; j < q_sz; j++)
			{
				int fr = G[i].front();
				G[i].pop();
				fr--;
				if (fr != 0) G[i].push(fr);
				else
				{
					if (!W[i].empty())
					{
						int W_fr = W[i].front();
						W[i].pop();
						G[i].push(W_fr);
					}
					fin++;
				}
			}
		}
		time++;
	}
	if (ans > time) ans = time;
}

 

(2) 큐를 한개를 이용하는 방법

 

 (1)번 방법보다 좀 더 코드가 간결하긴 하다. stair 큐의 사이즈를 3으로 고정하지 않아도 된다.

 

 stair의 사이즈를 3으로 고정하지 않고, 큐의 사이즈가 이미 3이라면 그 이후 부터는 

 

"들어가야할 Q(N)에 큐에 가장 먼저 들어간 Q(0)의 값을 더해서 넣는다."

 

이미 세명이 들어가 있다면 그 이후에 도착한 사람들은 기다려야 하는 데, wating 큐를 따로 만들어 주지 않고

기다려야할 시간을 더해서 큐에 넣어버리면 해결된다.  

 

void simulation()
{
	int time = 0;
	int fin = 0;
	for (int i = 0; i < P_sz; i++)
	{
		Arrive[i] = cal_dist(P[i].y, P[i].x, S[sel[i]].y, S[sel[i]].x)+1;
	}
	queue<int> G[2];
	while (1)
	{
		if (time > ans) return;
		if (fin == P_sz) break;
		for (int i = 0; i < P_sz; i++)
		{
			if (Arrive[i] == time)
			{
				if (G[sel[i]].size() < 3) G[sel[i]].push(S[sel[i]].K);
				else G[sel[i]].push(S[sel[i]].K+G[sel[i]].front());
			}
		}
		for (int i = 0; i < 2; i++)
		{
			int q_sz = G[i].size();
			for (int j = 0; j < q_sz; j++)
			{
				int fr = G[i].front();
				G[i].pop();
				fr--;
				if (fr != 0) G[i].push(fr);
				else fin++;
			}
		}
		time++;
	}
	if (ans > time) ans = time;
}

 

 SW모의고사 문제중에 푸는 데 시간이 가장 오래 걸렸던 것 같다.

시간에 따라서 시뮬레이션해야하는 문제 유형은 자주 나오니까 더  체화하려고 노력하자.

 

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF = 987654321;
struct person { int y, x; } P[10];
struct stair { int y, x, K;} S[2];
int S_sz,P_sz, ans, N;
int Arrive[10];
int A[10][10];

int sel[10];

void init()
{
	P_sz = 0,S_sz=0;
	ans = INF;
	memset(P,0, sizeof(P));
	memset(S, 0, sizeof(S));
	memset(sel, 0, sizeof(sel));
}

int cal_dist(int y,int x,int yy,int xx)
{
	return abs(y - yy) + abs(x - xx);
}

void simulation()
{
	int time = 0;
	int fin = 0;
	for (int i = 0; i < P_sz; i++)
	{
		Arrive[i] = cal_dist(P[i].y, P[i].x, S[sel[i]].y, S[sel[i]].x)+1;
	}
	queue<int> G[2], W[2];
	while (1)
	{
		if (time > ans) return;
		if (fin == P_sz) break;
		for (int i = 0; i < P_sz; i++)
		{
			if (Arrive[i] == time)
			{
				if (G[sel[i]].size() < 3) G[sel[i]].push(S[sel[i]].K);
				else W[sel[i]].push(S[sel[i]].K);
			}
		}
		for (int i = 0; i < 2; i++)
		{
			int q_sz = G[i].size();
			for (int j = 0; j < q_sz; j++)
			{
				int fr = G[i].front();
				G[i].pop();
				fr--;
				if (fr != 0) G[i].push(fr);
				else
				{
					if (!W[i].empty())
					{
						int W_fr = W[i].front();
						W[i].pop();
						G[i].push(W_fr);
					}
					fin++;
				}
			}
		}
		time++;
	}
	if (ans > time) ans = time;
}
void go(int cnt)
{
	if (cnt == P_sz)
	{
		simulation();
		return;
	}
	for (int i = 0; i < 2; i++)
	{
		sel[cnt] = i;
		go(cnt + 1);
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		init();
		scanf("%d", &N);
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				scanf("%d", &A[i][j]);
				if (A[i][j] == 1) P[P_sz++] = { i,j };
				else if (A[i][j] > 1) S[S_sz++] = { i,j,A[i][j] };
			}
		}
		go(0);
		printf("#%d %d\n",tc, ans);
	}
}