백준 3665, 최종 순위

개요

문제 링크
골드 1, Graph
m개 쌍의 전후관계가 바뀔 때 다른 쌍의 전후관계를 유지하며 변경 가능한지 출력하기

---

접근

1. 그래프의 개념이나 수학적 센스를 기르기 매우 좋은 문제. 우선 출력조건을 잘 보면 순위를 찾을 수 없는 경우 "?"를 출력하라고 나와있는데, 순위를 찾을 수 없는 경우는 존재하지 않는다.
2. 왜인지가 쉽게 생각되지 않는 이유는 "데이터에 일관성이 없다" 라는 말이 전혀 이해가 안되기 때문인데, 세 번째 테케를 이해하는 것부터 해보자.
   1. [1 2 3 4]에서 1,2 앞뒤가 바뀌고, 2,3, 3,4 바뀌면 엥 [4 3 2 1]이면 되는거 아님? 하고 생각할 수 있다. 하지만 핵심은 저 세 가지 바뀌는 관계 외에, 원래 존재하던 나머지 세 개 (1,3 / 1,4 / 2,4)의 전후관계가 유지되어야 한다는 것이다.
   2. [4 3 2 1]로 배치하면 1,3 / 1,4 / 2,4 의 전후관계가 모두 바뀌어버리기 때문에 [4 3 2 1]로 만들고 싶었다면 m=6이고 1,2부터 3,4까지 6개 쌍이 모두 들어갔어야 한다.
3. 자 그럼 문제로 다시 돌아와 "?"가 존재할 수 없는 이유에 대해 생각해보자. m개의 쌍의 순서에 변화를 줄 때, 나머지 쌍들의 관계를 해치지 않으면서 순서를 재배치하는 경우는 딱 하나만 존재하거나 존재하지 않는다. 존재한다고 가정하고 생각을 해보면 모순이 생기니 당연한 것이다.
4. 그럼 "?"는 출력하지 않아도 되는 것을 알겠고, 이제 안되는 경우를 생각해보자.
   1. 만약 [1 2 3]의 배치에서 3이 1보다 앞에 있도록 재배치한다고 생각해보자.

       // 바꾸려는 관계
       (1,3) --> (3,1)
       // 기존의 관계
       (1,2), (2,3)

      앞과 뒤를 이어서 원순열을 만든다? 4차원 공간이라면 가능하지 않을까...
   2. 결론은 3>1, 1>2, 2>3인 상황을 만들 수는 없다. 그런데 이거 어디서 많이 본 것 아닌가? 바로 사이클이다.
5. 그래서 모든 전후 관계에 변화를 주었을 때 사이클이 존재한다면 IMPOSSIBLE이다. 이제 구현을 하면서 시간을 줄여보자.
   1. 먼저 인접리스트로 풀어보자. 기존의 관계를 추가하는 방법은? i<j에 대해 adj[a[i]].push(a[j]) 를 해주면 된다. adj[i]는 i보다 뒤에 있는 원소의 모음이 되겠다.

       // set 사용
       for (int j=0;j<n;j++)
           for (int i=0;i<j;i++)
               adj[a[i]].insert(a[j]);

   2. 그런 다음 m번 인접리스트를 수정한다. a,b를 받아올 것인데, 만약에 b뒤에 a가 있다면? swap을 해주면 된다.

       while(m--) {
           int a,b;
           cin>>a>>b;
           if (adj[b].count(a)) swap(a,b); // b뒤에 a
           adj[a].erase(b);
           adj[b].insert(a);
       }

      그리고 DFS로 n개의 cycle을 찾아주면?

       bool dfs(adj,n,vis) {
           if (vis[n]) return 0;
           vis[n]=1;
           for (x:adj[n])
               if (!dfs(adj,x,vis))
                   return 0;
               vis[x]=0;
           return 1;
       }

      시원하게 시간초과다. 여기까지가 쉽게 할만한 생각이라 소개해봤다.
   3. 사실은 인접리스트를 사용하지 않아도 되는데, 우리가 궁금한 것은 a뒤에 무엇이 있는지가 아니라 몇개나 있는지에 대한 것이기 때문이다.
   4. 그래서 count 배열을 써보자. m번 배열을 수정하기 위해서는 a의 count는 하나 줄이고, b의 count는 하나 늘려주면 된다. a와 b의 swap조건은? a가 b의 뒤에 있을 때이다. 즉 b의 index가 더 작을 때.

       while(m--) {
           int a,b;
           cin>>a>>b;
           if (ind[b]<ind[a]) swap(a,b);
           cnt[b]++,cnt[a]--;
       }

   5. 그런 다음 사이클이 존재하는 조건이자, 유효하지 않을 조건은? count가 중복되는 경우이다. 자신보다 뒤에 오는 원소의 개수가 정확히 맨 뒤부터 0...n-1의 배열을 이루기 때문이다.

       for (int i=1;i<=n;i++) {
           if (s[cnt[i]]) {
               cout<<"IMPOSSIBLE\n";
               return;
           }
           s[cnt[i]]=i;
       }

   6. 그럼 배열을 어떻게 변형해야 하는지도 쉽게 생각할 수 있다. 뒤에 k개의 원소가 있는 수를 뒤에서 k번째에 위치하도록 만들어주면 된다.

---

Source code

// 2020KB, 12ms
#include <bits/stdc++.h>
using namespace std;

using vec=vector<int>;

void test() {
    int n;cin>>n;
    vec a(n),ind(n+1),cnt(n+1);
    for (int i=0;i<n;i++) {
        cin>>a[i],ind[a[i]]=i;
        cnt[a[i]]=n-i-1;
    }
    int m;cin>>m;
    while(m--) {
        int a,b;
        cin>>a>>b;
        if (ind[b]<ind[a]) swap(a,b);
        cnt[b]++,cnt[a]--;
    }
    vec s(n,0);
    for (int i=1;i<=n;i++) {
        if (s[cnt[i]]) {
            cout<<"IMPOSSIBLE\n";
            return;
        }
        s[cnt[i]]=i;
    }
    for (int i=n-1;i>=0;i--)
        cout<<s[i]<<" ";
    cout<<"\n";
}

int main() {
    cin.tie(0);ios::sync_with_stdio(0);
    int t;cin>>t;
    while(t--)test();
}

// 1124KB, 16ms
#include <stdio.h>
#define N 510

int a[N],ind[N],cnt[N],s[N];
void test() {
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        scanf("%d",a+i);
        ind[a[i]]=i,cnt[a[i]]=n-i-1;
        s[i]=0;
    }
    int m;
    scanf("%d",&m);
    while(m--) {
        int a,b,t;
        scanf("%d%d",&a,&b);
        if (ind[b]<ind[a])
            t=b,b=a,a=t;
        cnt[b]++,cnt[a]--;
    }
    for (int i=1;i<=n;i++) {
        if (s[cnt[i]]) {
            printf("IMPOSSIBLE\n");
            return;
        }
        s[cnt[i]]=i;
    }
    for (int i=n-1;i>=0;i--)
        printf("%d ",s[i]);
    printf("\n");
}

int main() {
    int t; scanf("%d",&t);
    while(t--) test();
}

# 31256KB, 148ms
import sys;input=sys.stdin.readline
def inp():return list(map(int,input().split()))
t=int(input())

for _ in range(t):
    n=int(input())
    a=inp()
    ind=[0]*(n+1);cnt=[0]*(n+1)
    for i,x in enumerate(a):
        ind[x]=i;cnt[x]=n-i-1
    m=int(input())
    for i in range(m):
        a,b=inp()
        if ind[b]<ind[a]:
            a,b=b,a
        cnt[b]+=1;cnt[a]-=1
    if any([i not in cnt for i in range(n)]):
        print("IMPOSSIBLE")
        continue;
    s=[0]*n
    for i,x in enumerate(cnt[1:]):
        s[x]=i+1
    print(' '.join(map(str,reversed(s))))