[c++] 백준 3665 - 최종 순위(그래프 정렬하기)

0. [c++] 백준  -

https://www.acmicpc.net/problem/3665

1. 풀이

그래프를 정렬하는 것을 처음 접해보아서 구글링을 조금 해서 도움을 받았다.

다양한 풀이가 존재하였지만, 내게 팍 와닿는 풀이법은 딱 한가지였다.

순위를 count배열을 활용하여 표현을 해놓는 것이었다.

우선 입력은 순위가 높은 순서로 들어오므로 그 순서대로 LastRank[a] = i+1로 배열에 넣어주었다.

그리고, Count[a]는 i번째 사람의 앞에 몇명이 있는지 저장하는 배열인데, 처음에는 i 명이 내 앞에 존재할 것이므로 Count[a] = i로 정의해주었다.

이후에는 변동 할 때마다 이전년도의 순위인 LastRank를 참고하여 순위에 맞게 Count를 변경시켜 주었다.

그리고, 그 카운터에 맟춰서 올해의 새로운 순위를 출력하게 문제를 구현하였다.

2. 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include<iostream> #include<algorithm>   using namespace std;   //작년 순위 int LastRank[501]; //자신의 앞에 있는 사람의 수 int Count[501]; //올해 순위를 정할때 활용. pair<int, int> Rank[501];   int main() {     int T, N, M;     int a, b;     cin >> T;     while (T--) {         cin >> N;         for (int i = 0; i < N; i++) {             //순서대로 입력을 받아서             cin >> a;             //이번 순서에 앞에 있는 사람의 수는 i이다.             Count[a] = i;             //그리고 이번 순서를 기록한다.(i+1)             LastRank[a] = i + 1;         }           //변동하는 순위들         cin >> M;         for (int i = 0; i < M; i++) {             cin >> a >> b;             //내 순위가 더 높았다면, count를 그대로 반영해주자.             if (LastRank[a] > LastRank[b]) {                 Count[a]--;                 Count[b]++;             }             else {                 Count[a]++;                 Count[b]--;             }         }           //내 이름?을 저장해주기 위해서 pair로 구현을 해준다. 앞은 Count 뒤는 내 이름         for (int i = 0; i < N; i++) {             Rank[i] = { Count[i+1], i + 1 };         }           //first를 기준으로 오름차순 정렬, 즉 순서대로 배열이 정렬된다.         sort(Rank, Rank + N);           //이번 배열중에 순위를 확정지을 수 있는지 확인한다.         bool isPossible = true;         for (int i = 0; i < N; i++) {             //만일 이번 순서의 Count가 i와 같지 않다면,             if (Rank[i].first != i) {                 //불가능한 배열이고 반복을 종료한다.                 isPossible = false;                 break;             }         }           if (!isPossible) {             cout << "IMPOSSIBLE" << endl;             continue;         }         //가능한 배열이라면 순서대로 이름을 출력해주면 완성!         for (int i = 0; i < N; i++) {             cout << Rank[i].second << " ";         }         cout << endl;     }         return 0; } Colored by Color Scripter

cs

3. 참고

https://blog.encrypted.gg/159

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!