BOJ 3665 최종 순위

사용한 알고리즘

위상정렬

알고리즘 설명

먼저 작년의 순위를 이용하여 그래프를 구성한다.
그래프 구성방법은 예제의 5,4,3,2,1 과 같은 순위같은 경우 5->4, 5->3, 5->2, 5->1, 4->3, 4->2, 4->1, …, 2->1 과 같다.
이 뒤에 작년과 달리 변경되는 순위가 들어온다. 두 순위 u,v 가 입력으로 주어지면 u와 v 간에 있던 그래프의 방향을 역뱡향으로 바꾼다. u->v 였다면 v->u로, v->u 였다면 u->v로 바꿔준다.
이 뒤에 위상정렬을 진행하는데, 큐의 크기가 2이상인 경우에는 순위가 불확실한 경우이며, 모든 순위가 정해 지기 전에 Q의 크기가 empty인 경우에는 cycle이 존재하는 조건으로 Impossible 조건이다.
위와 같은 알고리즘으로 위상정렬한 뒤에 출력한다.

풀이

// baekjoon 3665 yechan
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;

const int MAX_N=501;
int T, N, M;
int order[MAX_N];
int adj[MAX_N][MAX_N];
int ans[MAX_N];
int indeg[MAX_N];

int main() {
  scanf("%d", &T);
  while (T--) {
    memset(ans, 0, sizeof(ans));
    memset(adj, 0, sizeof(adj));
    memset(indeg, 0, sizeof(indeg));
    scanf("%d", &N);
    for (int i=0; i<N; i++) {
      scanf("%d", &order[i]);
    }
    // 작년 순위를 이용하여 연결 그래프 생성
    for (int i=0; i<N; i++) {
      for (int j=i+1; j<N; j++) {
        adj[order[i]][order[j]]=1;
        indeg[order[j]]++;
      }
    }

    scanf("%d", &M);
    while (M--) {
      int u, v;
      scanf("%d%d", &u, &v);
      // 역방향 간선 추가
      if (adj[u][v]) {
        adj[u][v] = 0;
        adj[v][u] = 1;
        indeg[u]++;
        indeg[v]--;
      } else {
        adj[v][u] = 0;
        adj[u][v] = 1;
        indeg[v]++;
        indeg[u]--;
      }
    }

    queue<int> q;
    // 큐에 시작 노드 추가 
    for (int i=1; i<=N; i++)
      if (!indeg[i])
        q.push(i);

    bool impossible = false;
    // 위상정렬 진행 (BFS)
    for (int i=1; i<=N; i++) {
      if (q.empty()) {
        impossible = true;
        break;
      }
      int cur = q.front();
      q.pop();
      // 큐의 크기가 2이상인 경우 순위 불확실(-1)
      if (q.size()) ans[i] = -1;
      else ans[i] = cur;

      for (int j=1; j<=N; j++) {
        if (!adj[cur][j]) continue;
        if (--indeg[j] == 0) {
          q.push(j);
        }
      }
    }

    if (impossible) {
      puts("IMPOSSIBLE");
    } else {
      for (int i=1; i<=N; i++) {
        // 값이 -1인 경우 순위 불확실 조건
        if (ans[i] == -1) {
          printf("? ");
        } else {
          printf("%d ", ans[i]);
        }
      }
      puts("");
    }
  }
  return 0;
}