2021 APC (아주대학교 프로그래밍) 대회 문제중 하나였다.
예전에 엘리베이터 관련 문제를 카카오 2차 기출에서 본 듯해서 그걸로 푸는건가? 했지만 해당 문제는 단지 dfs 탐색을 통해 일일이 체킹만 해주면 되는 문제이다.
다만 한가지 집고 넘어가야할 점이 있다. dfs 로 일일이 순회를 해주다가 해당 층에 사람이 없는 경우가 생기게 된다. 이렇게 되면 사람이 있는 층들 중에 한 곳으로 가야하는데 어떤 기준으로 갈 곳을 정해줄까? 에 대한 문제이다.
위상정렬 알고리즘에서 힌트를 가져왔다. 각 층을 원하는 사람의 수를 배열 하나 두어서 체킹해준 다음에 원하는 사람이 작은 층을 갈 곳으로 정하면 된다. 이렇게 되면 중간에 건너띄는 층 없이 모든 층을 깔끔하게 순회할 수 있기 때문이다. 이 점때문에 골드 2로 책정되지 않았나 생각이 든다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int arr[200000]; // 각 층을 원하는 사람의 수
int check[100002];
struct compare {
bool operator()(pii a, pii b) {
if (a.first == b.first)
return a.second > b.second;
return a.first > b.first;
}
};
vector<vector<int>> v;
priority_queue<pii, vector<pii>, compare> pq;
void dfs(int x, vector<int> &buf) {
if (check[x]) {
return;
}
check[x] = 1;
for (int i = 0; i < v[x].size(); i++) {
buf.push_back(v[x][i]);
dfs(v[x][i], buf);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int n, input;
cin >> n;
v = vector<vector<int>>(n + 1);
for (int i = 1; i <= n; i++) {
cin >> input;
v[i].push_back(input);
arr[input] += 1;
}
vector<int> tp;
dfs(1, tp);
for (int i = 1; i <= n; i++)
pq.push({ arr[i], i });
while (!pq.empty()) {
int cval = pq.top().first;
int cidx = pq.top().second;
pq.pop();
if (check[cidx]) continue;
tp.push_back(cidx);
dfs(cidx, tp);
}
cout << tp.size() << endl;
for (int i = 0; i < tp.size(); i++) {
cout << tp[i] << " ";
}
}https://www.acmicpc.net/problem/23296
23296번: 엘리베이터 조작
예제 1의 경우 1층에서 사람을 태워 4층으로 이동시켜 내려주고, 4층에서 사람을 태워 5층으로 이동시켜 내려주고, 5층에서 사람을 태워 2층으로 이동시켜 내려주고, 2층에서 사람을 태워 4층으로
www.acmicpc.net
'책장 > 알고리즘' 카테고리의 다른 글
| [백준-23295] 스터디 시간 정하기 1 (0) | 2021.11.05 |
|---|---|
| [백준-1939] 중량제한 (0) | 2021.10.21 |
| [백준-17135] 캐슬디팬스 (0) | 2021.10.03 |
| [백준-3020] 개똥벌레 (0) | 2021.10.01 |