[C++][SW Expert Academy] 점심 식사시간

문제

N*N 크기의 정사각형 모양의 방에 사람들이 앉아 있다.
점심을 먹기 위해 아래 층으로 내려가야 하는데, 밥을 빨리 먹기 위해 최대한 빠른 시간 내에 내려가야 한다.
방 안의 사람들은 P로, 계단 입구를 S라고 했을 때 [Fig. 1]은 사람의 위치와 계단 입구의 위치를 표시한 모습이다.

이동 완료 시간은 모든 사람들이 계단을 내려가 아래 층으로 이동을 완료한 시간이다.
사람들이 아래층으로 이동하는 시간은 계단 입구까지 이동 시간과 계단을 내려가는 시간이 포함된다.

    ① 계단 입구까지 이동 시간
        - 사람이 현재 위치에서 계단의 입구까지 이동하는데 걸리는 시간으로 다음과 같이 계산한다.
        - 이동 시간(분) = | PR - SR | + | PC - SC |
          (PR, PC : 사람 P의 세로위치, 가로위치, SR, SC : 계단 입구 S의 세로위치, 가로위치)

    ② 계단을 내려가는 시간
        - 계단을 내려가는 시간은 계단 입구에 도착한 후부터 계단을 완전히 내려갈 때까지의 시간이다.
        - 계단 입구에 도착하면, 1분 후 아래칸으로 내려 갈 수 있다.
        - 계단 위에는 동시에 최대 3명까지만 올라가 있을 수 있다.
        - 이미 계단을 3명이 내려가고 있는 경우, 그 중 한 명이 계단을 완전히 내려갈 때까지 계단 입구에서 대기해야 한다.
        - 계단마다 길이 K가 주어지며, 계단에 올라간 후 완전히 내려가는데 K 분이 걸린다.

사람의 위치와 계단 입구의 위치 및 계단의 길이 정보가 표시된 N*N 크기의 지도가 주어진다.
이때, 모든 사람들이 계단을 내려가 이동이 완료되는 시간이 최소가 되는 경우를 찾고,
그 때의 소요시간을 출력하는 프로그램을 작성하라.

 

풀이

계단의 입구에 도착했을때 바로 계산을 타는 것이 아닌, 1분 대기후 계산에 탑승하는것이 핵심이었습니다.

 

먼저 DFS를 통해 사람들이 계산을 탈 수 있는 모든 경우의 수를 구합니다.

 

for (int i = 0; i < groupedPeople.size(); i++) {
	// 시작 위치로부터 해당 계단 입구까지 도착 + 대기 시간(1s) 계산
	// 엘레베이터 실제 탑승은 이동후 1초 후이다.
	myQueue.push({ groupedPeople[i].x, groupedPeople[i].y, groupedPeople[i].time + 1 });
}

모든 사람이 어느 계단을 탈 지 결정된 상황에서 계단에 먼저 도착하는 사람 순서대로 Queue에 삽입해줍니다.

(계단을 내려가는 시간이 일정하기 때문에 먼저 도착한 사람이 무조건 먼저 내리게 됩니다.)

이때 (시작 위치로부터 해당 계단 입구까지 도착하는 시간 + 대기 시간(1s)) 정보를 함께 삽입합니다.

계단 실제 탑승은 이동후 1초 후이기 때문입니다.

 

int curTime = 1;
while (!myQueue.empty() || !stairs[n].myQueue.empty()) {
	// 내릴 시간이 되면 계단에서 내린다.
	while (!stairs[n].myQueue.empty()) { 
		if (stairs[n].myQueue.front().time == curTime) {
			stairs[n].myQueue.pop();
		}
		else break;
	}

	// 계단 탑승시 내려야 할 시각을 기록한다. 
	while (!myQueue.empty() && curTime >= myQueue.front().time && stairs[n].myQueue.size() < 3) {
		stairs[n].myQueue.push({ myQueue.front().x, myQueue.front().y, curTime + map[stairs[n].x][stairs[n].y] }); 
		myQueue.pop();
	}
	curTime++;
}

다음으로 1초부터 시간을 카운트하며 계단 탑승, 하차를 진행해줍니다.

계단 탑승 대기자 Queue, 계단 탑승자 Queue가 모두 빌 때까지 진행하게됩니다.

 

이때 누군가 내린다면 동시에 누군가 탈 수 있기 때문에 내리는 작업을 먼저, 타는 작업을 나중에 수행해줍니다.

 

// 0번 계단에 사람들 내려보내기
int first = calcStairs(0);
// 1번 계단에 사람들 내려보내기
int second = calcStairs(1);

int result = max(first, second);
if (result < answer) answer = result;

1번 계단을  탈때 소요되는 총 시간, 2번 계단을 탈때 소요되는 총 시간을 각각 구해줍니다.

두 사건은 독립사건이기 때문에 각 사건은 서로 영향을 주지않으며 두 케이스 중 더 큰 값이 해당 케이스의 소요시간이 됩니다.

 

전체 소스코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int N;
int map[510][510];

int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {-1, 0, 1, 0};

int windX;
int windY;
int windDir = 0;

int answer = 0;

bool IsInRange(int x, int y) {
	if (x >= 0 && x < N && y >= 0 && y < N) return true;
	else return false;
}

int move(int x, int y, int originalSand, double rate) {
	if (IsInRange(x, y)) map[x][y] += originalSand * rate;
	else answer += originalSand * rate;
	return originalSand * rate;
}

void moveAll(int windX, int windY, int windDir) {
	int originalSand = map[windX][windY];
	int blowSand = 0;

	if (windDir == 0) { // ←
		blowSand += move(windX - 2, windY, originalSand, 0.02);
		blowSand += move(windX - 1, windY - 1, originalSand, 0.1);
		blowSand += move(windX - 1, windY, originalSand, 0.07);
		blowSand += move(windX - 1, windY + 1, originalSand, 0.01);
		blowSand += move(windX, windY - 2, originalSand, 0.05);
		blowSand += move(windX + 1, windY - 1, originalSand, 0.1);
		blowSand += move(windX + 1, windY, originalSand, 0.07);
		blowSand += move(windX + 1, windY + 1, originalSand, 0.01);
		blowSand += move(windX + 2, windY, originalSand, 0.02);

		if (IsInRange(windX, windY - 1)) map[windX][windY - 1] += originalSand - blowSand;
		else answer += originalSand - blowSand;
	}
	else if (windDir == 1) {
		blowSand += move(windX - 1, windY - 1, originalSand, 0.01);
		blowSand += move(windX - 1, windY + 1, originalSand, 0.01);
		blowSand += move(windX, windY - 2, originalSand, 0.02);
		blowSand += move(windX, windY - 1, originalSand, 0.07);
		blowSand += move(windX, windY + 1, originalSand, 0.07);
		blowSand += move(windX, windY + 2, originalSand, 0.02);
		blowSand += move(windX + 1, windY - 1, originalSand, 0.1);
		blowSand += move(windX + 1, windY + 1, originalSand, 0.1);
		blowSand += move(windX + 2, windY, originalSand, 0.05);

		if (IsInRange(windX + 1, windY)) map[windX + 1][windY] += originalSand - blowSand;
		else answer += originalSand - blowSand;
	}
	else if (windDir == 2) {
		blowSand += move(windX - 2, windY, originalSand, 0.02);
		blowSand += move(windX - 1, windY - 1, originalSand, 0.01);
		blowSand += move(windX - 1, windY, originalSand, 0.07);
		blowSand += move(windX - 1, windY + 1, originalSand, 0.1);
		blowSand += move(windX, windY + 2, originalSand, 0.05);
		blowSand += move(windX + 1, windY - 1, originalSand, 0.01);
		blowSand += move(windX + 1, windY, originalSand, 0.07);
		blowSand += move(windX + 1, windY + 1, originalSand, 0.1);
		blowSand += move(windX + 2, windY, originalSand, 0.02);

		if (IsInRange(windX, windY + 1)) map[windX][windY + 1] += originalSand - blowSand;
		else answer += originalSand - blowSand;
	}
	else if (windDir == 3) {
		blowSand += move(windX - 2, windY, originalSand, 0.05);
		blowSand += move(windX - 1, windY - 1, originalSand, 0.1);
		blowSand += move(windX - 1, windY + 1, originalSand, 0.1);
		blowSand += move(windX, windY - 2, originalSand, 0.02);
		blowSand += move(windX, windY - 1, originalSand, 0.07);
		blowSand += move(windX, windY + 1, originalSand, 0.07);
		blowSand += move(windX, windY + 2, originalSand, 0.02);
		blowSand += move(windX + 1, windY - 1, originalSand, 0.01);
		blowSand += move(windX + 1, windY + 1, originalSand, 0.01);

		if (IsInRange(windX - 1, windY)) map[windX - 1][windY] += originalSand - blowSand;
		else answer += originalSand - blowSand;
	}
	map[windX][windY] = 0;
}

int main() {
	cin >> N;
	windX = N / 2;
	windY = N / 2;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}

	int cnt = 1;
	while (1) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < cnt; j++) {
				// 토네이도가 이동한다.
				windX = windX + dirX[windDir];
				windY = windY + dirY[windDir];

				moveAll(windX, windY, windDir);

				if (windX == 0 && windY == 0) break;
			}
			if (windX == 0 && windY == 0) break;
			windDir = (windDir + 1) % 4;
		}
		if (windX == 0 && windY == 0) break;
		cnt++;
	}

	cout << answer;

	return 0;
}