백준 2458 키 순서

문제설명

접근방식

우선 너무나도 명확하게 그래프 문제임은 알 수 있었고 어떻게 접근해야 하지라는 고민을 하다보니 꽤나 복잡하게 처리가 될 것 같지만 아이디어가 떠올랐다. 모든 정점끼리 간의 관계성 혹은 거리를 탐색해주면서 업데이트해주고 최종적으로 업데이트가 완료된 뒤에 자신을 제외한 모든 정점과 관계성이 있는 정점은 순위를 알 수 있는 것이고 하나의 정점이라도 관계성이 비어있는 정점이 있는 경우에는 순위를 알 수 없는 정점이 된다. 물론 핵심은 그 관계성을 어떻게 업데이트해주냐이다.

그래프는 키의 대소 관계로서 directed graph로 주어지긴 했지만 indegree, outdegree로 해서 양쪽 방향으로 이동은 가능하게 그래프의 정보를 가지고 있으면 가능할 것 같다는 생각이 든다. 그렇다면 모든 정점에서 한번씩 탐색을 해주는데 indegree방향으로는 인접한 정점끼리의 관계성만 보고 outdegree방향으로는 그 뒤의 정점들까지 더 탐색해가면서 다시 관계성을 업데이트 해주는 방식으로 접근했다. DFS로 접근하되 이미 들른 정점 체크를 해줄 수 없다는 것이 걱정이 됐으나 모든 정점이 대소관계를 가지므로 사이클이 생기지 않기도 하고 그 관계성을 계속해서 찾아가고 업데이트하는 것이 핵심이기에 적합하다고 판단했다.

1차 C++ 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

vector<vector<int>> relation;
vector<vector<int>> Bigger;
vector<vector<int>> Smaller;

void DFS(int cur, int diff, int org){
  relation[cur][org] = max(relation[cur][org], diff);
  relation[org][cur] = max(relation[org][cur], diff);

  for(int next : Smaller[cur])
    DFS(next, diff+1, org);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  //freopen("inp.txt", "r", stdin);
  
  int v, e;
  cin >> v >> e;
  relation.resize(v+1, vector<int>(v+1, 0));
  Bigger.resize(v+1);
  Smaller.resize(v+1);

  while(e--){
    int small, big;
    cin >> small >> big;
    Bigger[small].push_back(big);
    Smaller[big].push_back(small);
  }

  for(int i=1; i<=v; i++){
    for(int x : Bigger[i]){
      relation[i][x] = 1;
      relation[x][i] = 1;
    }

    for(int x : Smaller[i])
      DFS(x, 1, i);  
  }

  int ans = 0;
  for(int i=1; i<=v; i++){
    bool flag = true;
    for(int j=1; j<=v; j++){
      if(i!=j && relation[i][j]==0)
        flag = false;
    }
    if(flag)
     ans++;
  }
  cout << ans;
}

앞서 설명한 방식으로 나름대로의 규칙성에 맞게 잘 구현하고 예제 확인을 통해서 자신감을 얻고 제출했으나,,,

시간초과가 떠버렸다.
아마도 방문하지 않은 정점을 계속해서 업데이트하는 방식으로 구현했기 때문에 똑같은 관계성을 다시 탐색하고 해서 생기는 문제인것 같았다.

다시 머리를 비우고 어떤 방식으로 접근해야하나 생각해보았지만 각 정점간의 관계성을 업데이트하는 방식을 시간초과가 나지 않는 방식으로 구상하기 힘들었다. 빠르게 포기하고 검색을 하니 역시나 새로운 알고리즘이었다.

개념

플로이드-와샬(Floyd-Warshall) 알고리즘

// 플로이드-와샬 핵심내용
// 모든 정점을 중간 정점으로 한번씩 잡아서
// 다시 모든 정점을 시작과 끝으로 설정해 중간 정점을 거칠 때 최단경로가 발생하는 지 확인
for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

그래프에서 정점 간의 최단거리를 구하는 알고리즘들이 다양하게 존재하는데 대표적인 것으로는 다익스트라, 벨먼포드 알고리즘이 있는데 두 알고리즘은 "한 정점에서 모든 정점까지의 최단거리"를 구하는 알고리즘이다. 하지만 현재 문제에서 요구하는 것은 거리의 값 자체가 중요한 것은 아니지만 거리로 표상되는 모든 정점 간의 관계성이고 "모든 정점에서 모든 정점까지의 최단거리"를 구하는 알고리즘인 플로이드-와샬 알고리즘을 적용할 수 있는 것이다.

알고리즘 자체에 대한 설명은 좋은 포스트 글들이 있이므로 링크로 남기도록 한다.

플로이드-와샬 알고리즘

모든 정점 간의 거리(관계성) 파악해주기라는 핵심요소는 이해했다는 점.
이를 비록 무식한 방식이지만 나름 이해하고 자신만의 방식으로 시도를 해봤다는 점.
그리고 이를 해결해주는 좋은 알고리즘을 알게 되었다는 점.
여러모로 한 문제 안에서 얻어가는 것이 많은 문제였다.

정답 C++ 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair <ll, ll>;

#define INF 40000

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  //freopen("inp.txt", "r", stdin);
  
  int v, e;
  cin >> v >> e;
  vector<vector<int>> relation(v+1, vector<int>(v+1, INF));
  
  for(int i=1; i<=v; i++)
    relation[i][i] = 0;

  while(e--){
    int small, big;
    cin >> small >> big;
    relation[small][big] = 1;
  }

  for(int mid=1; mid<=v; mid++){
    for(int src=1; src<=v; src++){
      for(int dst=1; dst<=v; dst++)
        relation[src][dst] = min(relation[src][dst], relation[src][mid]+relation[mid][dst]); 
    }
  }

  int ans = 0;
  for(int i=1; i<=v; i++){
    bool flag = true;
    for(int j=1; j<=v; j++){
      if(relation[i][j]==INF && relation[j][i] == INF)
        flag = false;
    }
    if(flag)
     ans++;
  }
  cout << ans;
}