← All Articles

[BAEKJOON] 17616. 등수 찾기

Posted on

문제 :

KOI 본선 대회에 N명의 학생이 참가했다. 이 학생들을 각각 1부터 N까지 정수로 표현하자. 대회가 끝나고 성적을 발표하는데, 이 대회는 전체 학생의 등수를 발표 하는 대신, 두 학생 A, B가 대회 본부에 찾아가면 본부는 두 학생 중 어느 학생이 더 잘 했는지를 알려준다. 둘 이상의 학생이 동점인 경우는 없다.

자신의 전체에서 등수가 궁금한 학생들은 둘 씩 짝을 지어서 대회 본부에 총 M번 질문을 했다. 여러분은 등수를 알고 싶은 학생 X와 대회 본부의 질문에 대한 답들 로부터 이 학생 X의 등수 범위를 찾아서 출력한다. 질문에 대한 답으로 알 수 있는 최대한 정확한 답을 출력한다.


입력 :

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어지는데, 이 뜻은 학생 A가 학생 B보다 더 잘했다는 뜻이다. 같은 A, B가 둘 이상의 줄에 주어지는 경우는 없고, 입력된 값이 정확함이 보장된다.


출력 :

표준 출력으로 두 정수 U, V (1 ≤ U ≤ V ≤ N)를 출력한다. 이는 학생 X의 가능한 가장 높은 등수가 U, 가능한 가장 낮은 등수가 V임을 나타낸다. 만약 학생 X의 가능한 등수가 정확하게 하나라면, U = V이다.



풀이 :

순위가 둘 중 어느 학생이 높은지에 관한 정보가 담긴 쌍이 여러 개 주어지는 것을 보고 위상정렬로 접근해야할 것이라고 예상했다.

하지만 해당 학생이 최소 몇 등부터, 최대 몇 등까지 가능한지 범위를 구해줘야 했기 때문에 단순한 위상정렬 알고리즘으로는 해결할 수 없을 것이라 판단했다. 그래서 위상정렬을 방향을 역으로 해서 한 번 더 실행해 총 두번의 위상정렬 탐색(bfs)으로 해답을 구할 수 있는 방법을 구상했다.


세부 구현사항 :

  1. 방향성을 가지는 topological sort adj 배열을 두개 준비한다. loweradj의 경우 자신보다 낮은 순위로 방향을 가지는 인접행렬을 구성하고, higheradj의 경우 자신보다 높은 순위로 방향을 가지는 인접행렬을 구성한다.
  2. 해당 학생의 최대 순위를 저장하는 highestrank, 최소 순위를 저장하는 lowestrank 변수를 준비해 각각 1, n 으로 초기화한다.
  3. 해당 학생보다 낮은 순위를 가지는 학생의 수를 loweradj 인접 벡터의 위상정렬 탐색을 통해 구한 후 lowestrank의 값에 빼준다.
  4. 해당 학생보다 높은 순위를 가지는 학생의 수는 higheradj 인접 벡터의 위상정렬 탐색을 통해 구한 후 highestrank의 값에 더해준다.

다음의 방식으로 위상정렬 탐색(bfs) 두 번 으로 순위 범위의 해답을 얻을 수 있다.



코드 :

코드 보기/접기 
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
vector<vector<int>> loweradj, higheradj;
int n, orgstu;

int bfs(bool isloweradj) {
    vector<vector<int>> adj;
    queue<int> q;
    bool *used = new bool[n + 1]{false};
    int count = 0;

    q.push(orgstu);
    used[orgstu] = true;
    adj = (isloweradj) ? loweradj : higheradj;

    while (!q.empty()) {
        int curidx = q.front();
        q.pop();

        int size = adj[curidx].size();
        for (int k = 0; k < size; k++) {
            int cmpidx = adj[curidx][k];
            if (used[cmpidx]) continue;
            q.push(cmpidx);
            used[cmpidx] = true;
            count++;
        }
    }

    return count;
}

int main() {
    int m, fir, sec;

    cin >> n >> m >> orgstu;
    int highestrank = 1, lowestrank = n;

    loweradj.resize(n + 1);
    higheradj.resize(n + 1);

    while (m--) {
        cin >> fir >> sec;
        loweradj[fir].push_back(sec);
        higheradj[sec].push_back(fir);
    }

    lowestrank -= bfs(true);
    highestrank += bfs(false);

    cout << highestrank << ' ' << lowestrank << '\n';

    return 0;
}


AlgorithmalgorithmbaekjoonC++