2383. 점심 식사시간

static int N;
static int board[10][10];
static int choice[10];
static vector<pair<int, int>> people;
static vector<pair<int, int>> stairs;
static int ans;

static int simulation()
{
	int timer[10], total = people.size(), t;
	queue<int> q, qq[2];
	int state[10];

	for (int i = 0; i < people.size(); i++)
	{
		int which = choice[i];
		int dy = people[i].first - stairs[which].first; 
		int dx = people[i].second - stairs[which].second;
		timer[i] = abs(dy) + abs(dx); //해당 계단 까지 가는데 필요한 시간
		q.push(i);
	}

	for (t = 0; total > 0 && t < ans; t++)
	{
		//먼저 계단 입구로 향하는 사람들에 대해서
		int sz = q.size();
		for (int cnt = 0; cnt < sz; cnt++)
		{
			int p = q.front();
			q.pop();

			if (timer[p] == 0) //타이머가 만료되었다면,
			{
				int which = choice[p];
				if (qq[which].size() < 3) //계단 입구에 들어 갈 수 있다면
				{
					qq[which].push(p);
					//타이머 재설정, 시작위치가 계단일 수 있다.
					timer[p] = board[stairs[which].first][stairs[which].second];
				}
				else //없다면
					q.push(p); //다시 대기
			}
			else //타이머를 동작 시켜야 한다면
			{
				timer[p] -= 1;
				q.push(p);
			}
		}

		//모든 계단에 대해서
		for (int i = 0; i < 2; i++)
		{
			int sz = qq[i].size();
			for (int cnt = 0; cnt < sz; cnt++)
			{
				int p = qq[i].front();
				qq[i].pop();

				timer[p] -= 1; //먼저 하는 이유, 
				if (timer[p] == 0) //다음 시간 대에 다름 사람을 계단에 진입 시켜주기 위함
					total -= 1;
				else
					qq[i].push(p);
			}
		}
		
	}

	return t + 1; //1을 더해야 하는 이유?
}

static void __solution(int p)
{
	if (p >= people.size())
	{
		int ret = simulation();
		if (ret < ans)
			ans = ret;
	}
	else
	{
		//모든 조합을 만듬
		for (int i = 0; i < 2; i++)
		{
			choice[p] = i;
			__solution(p + 1);
		}
	}
}

static int solution()
{
	scanf("%d", &N);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			scanf("%d", &board[y][x]);
			if (board[y][x] == 1) //사람
				people.push_back({ y, x });
			if (board[y][x] > 1) //계단
				stairs.push_back({ y, x });
		}
	}

	ans = 0x7fffffff; //초기화
	__solution(0);
	people.clear(); //초기화
	stairs.clear(); //초기화
	return ans;
}

처음에는 예전에 생각했지만 구현하지 않았던, 각각의 계단 입구에서 제일 가까운 세명의 위치만 고정하고 나머지는 재귀로 모든 경우를 만들 후 시뮬레이션을 해보는 방법으로 코드를 구현해보았다. 해당 방식을 구현하는 것에는 생각보다 처리할 것이 많아 시간이 좀 걸렸지만, 거기까지는 구현을 하였다.

그러나 시뮬레이션에서 문제가 생겨 답이 자꾸 틀렸다. 이 경우 디버깅 시간이 부족할 수 있으니,

가급적 모든 경우를 다 고려하는 것 만 생각해야 겠다.

 

그래서 예전에 짰었던 코드를 다시 참조하였는데, 해당 코드는 답은 맞았으나, 다시 보니 불필요하게 작성된 코드도 많았으며, 결정적으로 동작 방식이 잘못되었다. 

 

그래서 기존에 생각했던 방법을 취소하고, 모든 조합을 만들면서 시뮬레이션 하도록 코드를 다시 작성하며 이전 코드에서 잘못된 부분을 수정하여 다시 테스트하였지만, 또 답이 틀리는 문제가 있었고,

서버에서 테스트 시 VS와 달리 타임아웃이 발생하는 문제가 있었다.

 

그래서 코드 자체에 문제로 보고 코드를 다시 읽어보았는데, 한참후에나 잘못된 부분을 찾았다.

simulation에서 첫번째 반복문에서 stairs의 row인덱스를 which로 하여 접근해야 하는데,

사람의 번호 인 i로 접근하도록 작성되어 있었다.

이 부분을 수정하고, 시뮬레이션이 정확히 동작할 수 있도록 코드를 다시 작성하였다.

 

예제의 첫번째 테스트 케이스 중 사람 3번에 대해서 동작 방식을 이해하면

 

0분 (2, 3) -> (2, 4)

1분 (2, 4) -> (2, 5)

2분 (2, 5) : 계단 입구에 도착

3분 계단을 내려감 : 3 -> 2

4분 계단을 내려감 : 2 -> 1

5분 계단을 내려감 : 1 -> 0, total -= 1 해서 0이 된다.

6분 이동 완료. t++ 후 total을 검사 한다.

 

5분에서 timer가 0이 됨을 알 수 있다. 그러나 다음 시간대에도 해당 사람이 계단에 남아있다면,

계단 입구에서 들어가기를 희망하는 사람에 대한 처리가 늦어 질 수 있다.

그래서 timer를 바로바로 동작 시키고, 0이 되면 큐에서 빼는 것이다.

 

for문이 끝나고 해당 t를 바로 반환하면 항상 정답보다 1이 작은 값이 출력되어

t+1을 반환하여 마무리함.

 

시작위치가 계단 입구인 경우는 없다.

 

/*정답이 좀 이상한듯, 계단입구에 도착한 즉시 타이머가 동작해야 pass가 되는데,

원래는 qq에 들어가는 시간 대와, qq에 대한 타이머동작이 같은 시간에 일어남,

즉, qq에 들어간 시점에서는 qq에 대해 검사할 때, state를 보고 타이머만 설정하는게 맞는 것 같다.*/

 

 

//주의사항 및 정리

1. 실제 시험에서는 5초가 걸리더라도 일단 패스되게 하는 것이 첫번째 이므로 모든 경우를 다 체크하였을 때, 패스가 되면 바로 다음 문제로 넘어가거나, 두문제 다 풀고 난 뒤에 시간을 단축할 방법을 생각해야만 한다.

2. 요새 시뮬레이션 유형의 문제가 잘 안풀리는 것 같다. 그 이유로는 예전에 풀었던 기억에 의존하기 때문이 첫번째이며, 두번째는 여러 상황간에 연관성을 그림으로 그리지 않고 머리속으로만 상상하기 때문인 것 같다. 딱 한가지 경우에 대해서 위와 같이 글로라도 적어 두면 더 나을 것 같다. 그리고 항상 상황을 나누어서 if ~ else로 처리 할 것, 한 순간에 한가지 상황만 처리 할 수 있기 때문이다.

3. 이어 적으면 예제로 나온 그림과 같이 동작 방식을 정리 할 것. 

4. 시작 위치가 계단이라면, t=0 인 순간 부터 계단에서 내려가는 타이머가 동작 할 수 도 있다. -> 이런 경우는 없다.