static int N;
static int board[10][10];
static int ans;
static int stairs[2][3]; //계단의 개수는 두개, y, x, 계단 길이
static int persons[10]; //어느 계단을 선택 할 지,
static int simulation(void)
{
int cpy[10][10];
int target[10][10];
int tot = 0, t = 0;
queue<pair<int, int>> q; //계단입구로 향하는 좌표
queue<pair<int, int>> qq[2]; //계단을 내려가는 좌표
memcpy(cpy, board, sizeof(cpy));
for (int y = 0; y < N && t < N; y++)
{
for (int x = 0; x < N && t < N; x++)
{
if (cpy[y][x] == 1) //먼저 사람들의 위치를 찾고,
{
int which = persons[t++];
cpy[y][x] = (abs(y - stairs[which][0]) + abs(x - stairs[which][1])); //필요한 시간,
q.push({ y, x });
target[y][x] = which; //해당 위치에 사람이 들어갈 계단 입구를 설정,
}
}
}
tot = t; //사람의 수,
for (t = 1; tot > 0 && t < ans; t++) //시간이 흐름, 모든 사람이 존재한다면 반복,
{
int q_sz = q.size();
for (int i = 0; i < q_sz; i++) //계단입구로 향하는 중
{
pair<int, int> cur = q.front();
q.pop();
if (cpy[cur.first][cur.second] > 0) //계속 이동해야 한다면,
{
cpy[cur.first][cur.second] -= 1;
q.push(cur);
}
else if (cpy[cur.first][cur.second] == 0) //계단 입구에 도착,
{
int which = target[cur.first][cur.second];
if (qq[which].size() < 3) //계단에 들어 갈 수 있다면
{
cpy[cur.first][cur.second] = stairs[which][2];
qq[which].push(cur);
}
else //없다면 대기,
q.push(cur);
}
}
for (int i = 0; i < 2; i++) //모든 계단 입구에 대해서
{
q_sz = qq[i].size();
for (int j = 0; j < q_sz; j++) //계단 입구에서 아래층으로 내려가는 중,
{
pair<int, int> cur = qq[i].front();
qq[i].pop();
cpy[cur.first][cur.second] -= 1;
if (cpy[cur.first][cur.second] == 0) //아래층에 도착,
tot -= 1; //해당 사람은 탈출하여 사람 수를 줄임,
else //내려가야할 계단이 아직 남음,
qq[i].push(cur);
}
}
}
return t;
}
static void __solution(int p)
{
if (p == 10)
{
int ret = simulation(); //배치한 대로 이동시켜봄,
if (ret < ans)
ans = ret;
}
else
{
for (int i = 0; i < 2; i++) //사람들이 갈 수 있는 계단 입구의 배치를 생성,
{
persons[p] = i;
__solution(p + 1);
}
}
}
static int solution(void)
{
int tmp = 0;
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) //계단입구,
{
stairs[tmp][0] = y;
stairs[tmp][1] = x;
stairs[tmp++][2] = board[y][x];
}
}
}
ans = 0x7FFFFFFF;
__solution(0);
return ans;
}코드의 동작 방식은 주석으로 대체하고,
몇가지 생각해 볼 만한 점에 대해서만 정리해보겠다.
2477번 문제와 비슷한 형식으로 풀었다.
그래서 처음에는 simulation()에서 계단 입구로 향하는 반복문에서 계단입구에 도착한 순간 해당 계단의 큐에 push할 수 있으면 push하는 방식으로 코드를 작성하였다.
그러나 2477번과 달리 이번 문제에서는 한순간에 하나만 할 수 있다.
즉, 이러한 방식으로 코드를 작성하면 한순간에 계단 입구에 도착한 순간 바로 계단을 내려가버리는 식으로 모델링이 되되기 때문에 이러한 방식이 아닌 도착하고, 그 다음 시간대에 계단에 들어가게 하는 식으로 작성했다.
두번째는 실행시간에 대한 고찰이다.
위 코드는 꽤나 오랜 시간이 걸린다. 당연하게도 모든 경우에 대해 전부 체크하기 때문이다.
그래서 매우 큰 N에 대해서는 효과적이지 못하다.
하지만 문제 조건을 따져 보았을 때에 나름 할만하였고, 더욱이 최소값을 찾는 문제에서는 간결하게 코드를 구성하기보다는 최대한 실수 없이 모든 경우를 따져보는 것이 제한된 시간내에 빠르게 코드를 작성 할 수 있기 때문이다.
//
각 계단 당 최대 3명 까지는 동시 입장이 가능하기 때문에,
최대 10명에 대해서, 그 중 6명은 향할 계단 입구가 정해지므로,(각 계단에서 가장 가까운 3명씩)
나머지 4명에 대해서만 순열로 이를 정해줄 수 있다.
즉, simulation()를 1024 -> 16 으로 그 실행 횟수를 확 낮춰 줄 수는 있다.
