[백준-23296] 엘리베이터 조작

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번: 엘리베이터 조작