문제
문제 접근
완전 탐색 문제이다.
관건 1. 완전 탐색이 필요한 포인트
모든 사람들이 계단을 내려가 이동이 완료되는 시간이 최소가 되는 경우를 찾아야 함.
그러기 위해서는 '사람-계단' 의 모든 경우의 수에 대해 시뮬레이션을 해야 한다.
따라서 '사람-계단' 쌍을 찾는 알고리즘을 dfs로 구현한 뒤, 다 찾을 경우 계단을 내려가는 시간을 구하도록 했다.
관건 2. 사람들은 계단을 동시에 내려간다
이 문제는 한 계단에 최대 3명이 있을 수 있다.
계단에 있는 총 인원이 3명일 경우, 계단 입구에서 기다리는 로직을 단순히 사용하게 되면 다음과 같은 오류가 발생한다.
t 타임에 A가 계단을 빠져나가는 상황이다. A가 계단을 빠져나가기 전에 B가 계단 입구에서 계단을 내려가는 걸 시도하는 경우 실제로는 내려갈 수 있는 상황이지만 계단에 있는 사람이 (A를 포함하여)3명으로 계산되기 때문에 내려갈 수 없게 된다.
이를 해결하기 위해 우선순위 큐를 사용.
계단까지의 거리가 가까운 순대로 정렬하여 순서대로 동작을 수행하도록 했다.
이 경우, 곧 빠져나갈 사람의 거리가 제일 적으므로 가장 먼저 동작을 수행한다. 즉, 계단을 빠져나가게 된다.
그러면 같은 시간대에 계단 입구에서 대기하던 사람이 계단을 내려갈 수 있게 된다.
관건 3. 우선순위 큐
우선순위 큐는 앞서 언급했던 오류를 해결하기 위해 사용될 뿐만 아니라 최초 위치에서 계단까지의 최소 거리를 계산해서 차례로 도달하게 만드는 동작을 위해서도 사용된다.
compute_time 함수의 while문 내에서 우선순위 큐를 활용하여 아직 이동이 남은 사람들을 정렬한 후, 한 칸씩 이동하는 동작을 모든 사람의 이동이 종료될 때까지 반복한다.
문제 흐름
- 모든 사람이 어느 계단으로 내려갈지를 정한다. 다 정해지면 이동이 시작된다.
- 사람들은 1분마다 계단까지 한 칸 움직일 수 있으며, 계단 입구에 도착할 경우 다음 턴에 계단을 내려갈 수 있다.
계단 위에는 최대 3명이 있을 수 있으며, 계단에 이미 3명이 있을 경우 계단 입구에서 대기해야 한다. - 마지막 사람이 계단을 다 내려왔을 때 수행을 종료한다.
풀이
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <limits.h>
#define A 0
#define B 1
using namespace std;
typedef struct people {
int num;
int x;
int y;
int len;
int stair;
bool done;
} people;
typedef struct stair {
int x;
int y;
int len;
int cnt;
} stair;
vector<stair> Stair;
struct cmp {
bool operator()(people a, people b) {
return (a.len - Stair[a.stair].len) > (b.len - Stair[b.stair].len); // 계단까지의 거리가 가까운 순서대로 정렬
}
};
int T, N, rst;
int is_visit[10];
vector<people> People;
priority_queue<people, vector<people>, cmp> PQ;
void input() {
cin >> N;
People.clear();
Stair.clear();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int tmp;
cin >> tmp;
if (tmp != 0) {
if (tmp == 1) {
people tmp;
tmp.num = People.size(); tmp.x = i; tmp.y = j;
People.push_back(tmp);
}
else {
Stair.push_back({ i, j, tmp ,0 });
}
}
}
}
rst = INT_MAX;
memset(is_visit, 0, sizeof(is_visit));
}
int everyone_done() {
for (int i = 0; i < People.size(); i++)
if (!People[i].done) return false;
return true;
}
void compute_time() {
int k = 0;
while (true) {
if (everyone_done()) {
rst = min(rst, k);
break;
}
k++;
for (int i = 0; i < People.size(); i++) {
if(People[i].done != true) PQ.push(People[i]);
}
while (!PQ.empty()) {
int i = PQ.top().num; PQ.pop();
if (People[i].len > 0) { // 계단을 내려가는 중인 경우
if (People[i].len == Stair[People[i].stair].len) { // 계단 입구에서 내려가는 걸 시도
if (Stair[People[i].stair].cnt < 3) { // 내가 내려가고자 하는 계단에 사람이 3명 이하이면 계단을 내려가기 시작
Stair[People[i].stair].cnt++;
People[i].len--;
}
}
else {
People[i].len--;
}
}
else { // 계단을 다 내려간 경우
Stair[People[i].stair].cnt--;
People[i].done = true;
}
}
}
}
void set_info() {
for (int i = 0; i < People.size(); i++) {
int s = People[i].stair;
People[i].len = abs(People[i].x - Stair[s].x) + abs(People[i].y - Stair[s].y) + Stair[s].len;
People[i].done = false;
}
}
void dfs(int person, int stair, int cnt) {
People[person].stair = stair;
if (cnt == People.size()) {
set_info();
compute_time();
return;
}
for (int i = person + 1; i < People.size(); i++) {
if (!is_visit[i]) {
is_visit[i] = 1;
dfs(i, A, cnt + 1);
dfs(i, B, cnt + 1);
is_visit[i] = 0;
}
}
}
void solve() {
for (int i = 0; i < People.size(); i++) {
is_visit[i] = 1;
dfs(i, A, 1);
dfs(i, B, 1);
is_visit[i] = 0;
}
}
int main() {
cin >> T;
for (int tc = 1; tc <= T; tc++) {
input();
solve();
cout << "#" << tc << " " << rst << endl;
}
}우선순위 큐 좋은 자료구조다..
