[백준/C++] 최종 순위 (No. 3665)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 풀기 전에 위상 정렬 문제를 풀었었다.

 

위상 정렬의 특징은 정렬할 때, 특정 노드로 들어오는 간선의 수를 이용하면 노드간의 상대적인 우선 순위를 이용해 정렬을 할 수 있다는 특징이 있었다.

 

그래서 이 문제도 위상정렬의 특징을 이용해 풀었다.

 

이 문제의 핵심은 모든 팀의 확실한 순위를 알게 되는지 판단하는 것이다.

 

확실한 순위를 알기 위해서는 처음에 특정 노드로 들어오는 간선이 0인 노드가 1개여야하며, 서로 다른 팀 간에 우선순위를 확실하게 알아야 하기 때문에 특정 노드에서 출발하는 간선을 하나씩 지울때 마다 들어오는 간선이 0인 노드가 하나만 생기게 된다.

 

왜냐하면 특정 노드에서 출발하는 간선을 지웠는데 들어오는 간선이 0인 노드가 여러개라면, 들어오는 간선이 0인 노드들 사이에서 어떤 노드가 우선순위가 더 높은지 모르기 때문이다.

즉, 어떤 팀의 순위가 더 높은지 알 수 없게 된다.

 

그러므로 순위가 바뀐 팀들의 정보를 이용해 간선의 수를 갱신하고, 갱신된 정보를 이용해 팀의 순위를 파악해 나가며 우선순위가 정확하지 않은 팀들이 생기면 IMPOSSIBLE을 출력하면 된다.

 

이제 풀이 방법을 알았으니 작년의 순위를 이용해 문제를 풀면된다.

 

그러면 어떻게 작년의 순위를 이용해 그래프를 만들 수 있을까?

 

먼저 작년에 1위였던 팀은 들어오는 간선이 하나도 없다.

왜냐하면 1위이기 때문에 앞에 있을 팀이 하나도 없기 때문이다.

 

마찬가지로 작년에 2위였던 팀은 들어오는 간선이 하나만 있다.

왜냐하면 1위였던 팀이 앞에 있기 때문이다.

 

이를 이용하면 작년에 N위였던 팀은 들어오는 간선이 N-1개 있게 된다.

 

이번년도의 정보를 갱신하는 방법도 마찬가지다.

 

팀 A와 팀 B의 순위가 바뀌면 작년에 순위가 높았던 팀은 순위가 낮아지므로 앞에 들어오는 간선이 1개 늘어나고, 작년에 순위가 낮았던 팀은 순위가 높아지므로 들어오는 간선이 1개 줄어든다.

 

이러한 점을 이용해 정보를 갱신해 나가면서 팀들 간의 순위를 파악하면 문제를 해결할 수 있다. 

(N개의 팀에 대해 들어오는 간선의 수가 (0 ~ N-1) 사이의 수가 1개씩만 존재하면 모든 팀의 등수를 알 수 있게 된다) 

 

​

[아이디어 정리]

1. 작년에 등수가 i번째인 팀은 자신보다 순위가 높은 팀이 i-1개 있다.
2. 이번년도에 A팀과 B팀의 순위가 바뀌었다면, 작년의 순위를 비교한 뒤, 작년에 순위가 높았던 팀은 들어오는 간선의 수를 1증가시키고, 작년에 순위가 낮았던 팀은 들어오는 간선의 수를 1감소시킨다.
3. 모든 정보를 갱신한 다음 N개의 팀들에 대해 들어오는 간선의 수가 0 ~ N-1 사이에서 겹치면 IMPOSSIBLE, 하나도 겹치지 않으면 순위를 확실히 알 수 있으므로 순위를 출력한다.

 

 

Code (간선의 수만 이용)

 

 

#include <iostream>
#include <vector>
using namespace std;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int tc;
    cin >> tc;
    for (int t = 0; t < tc; t++)
    {
        int n;
        cin >> n;
        vector<int> V(n + 1); //순위
        vector<int> inCome(n + 1, 0);
        int nowN;
        for (int i = 1; i <= n; i++) {
            cin >> nowN;
            V[nowN] = i; // 순위
            inCome[nowN] = i - 1;
        }
        int m, st, ed;
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> st >> ed;
            if (V[st] < V[ed])// 원래 st가 ed 앞이라면
            {
                inCome[st] += 1;
                inCome[ed] -= 1;
            }
            else
            {
                inCome[ed] += 1;
                inCome[st] -= 1;
            }
        }
        vector<int> visited(n+1,-1);
        bool flag = true;
        for (int i = 1; i <= n; i++) {
            if (visited[inCome[i]]==-1){
                visited[inCome[i]] = i;
            }
            else {
                flag = false;
                break;
            }
        }

        if (!flag) {
            cout << "IMPOSSIBLE\n";
        }
        else {
            for (int i = 0; i < n; i++) {
                cout << visited[i] << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}

 

 

 

Code (간선 직접 생성)

 

 

#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int tc;
    cin >> tc;
    for (int t = 0; t < tc; t++)
    {
        int n;
        cin >> n;
        vector<int> V(n + 1);
        vector<set<int>> graph(n + 1);
        vector<int> inCome(n + 1, 0);
        int nowN;
        for (int i = 1; i <= n; i++) {
            cin >> nowN;
            V[i] = nowN;
            for (int j = 1; j < i; j++)
            {
                graph[V[j]].insert(V[i]);
            }
            inCome[nowN] = i - 1;
        }
        queue<int> ans;
        int m, st, ed;
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> st >> ed;
            if (graph[st].find(ed) != graph[st].end())// st가 ed 앞이라면
            {
                graph[st].erase(ed);
                graph[ed].insert(st);
                inCome[st] += 1;
                inCome[ed] -= 1;
            }
            else
            {
                graph[ed].erase(st);
                graph[st].insert(ed);
                inCome[ed] += 1;
                inCome[st] -= 1;
            }
        }
        queue<int> tmpQ;
        for (int i = 1; i <= n; i++) {
            if (inCome[i] == 0) {
                tmpQ.push(i);
            }
        }
        while (!tmpQ.empty()) {
            if (tmpQ.size() > 1) {
                break;
            }
            nowN = tmpQ.front();
            tmpQ.pop();
            ans.push(nowN);
            for (set<int>::iterator it = graph[nowN].begin(); it != graph[nowN].end(); it++)
            {
                inCome[*it] -= 1;
                if (inCome[*it] == 0) {
                    tmpQ.push(*it);
                }
            }
        }
        if (ans.size() != n) {
            cout << "IMPOSSIBLE\n";
        }
        else {
            while (!ans.empty()) {
                cout << ans.front() << " ";
                ans.pop();
            }
            cout << "\n";
        }
    }
    return 0;
}

 

---

 

처음에는 간선의 수만 세도 된다는 생각이 들지 않아서 직접 그래프의 간선을 만들어 문제를 해결했다.

나중에 생각해보니 이번년도에 순위가 바뀐 팀에 대해 정보가 누락이 될 수는 있지만, 중복해서 등장하거나 이상한 정보가 들어오는 경우는 없기 때문에 간선의 수를 세기만 해도 문제를 풀 수 있었다.

 

요즘 문제 푸는게 많이 뜸해졌는데 그래도 이틀에 한 문제는 풀도록 다시 시작해야겠다...

 

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