우선 너무나도 명확하게 그래프 문제임은 알 수 있었고 어떻게 접근해야 하지라는 고민을 하다보니 꽤나 복잡하게 처리가 될 것 같지만 아이디어가 떠올랐다. 모든 정점끼리 간의 관계성 혹은 거리를 탐색해주면서 업데이트해주고 최종적으로 업데이트가 완료된 뒤에 자신을 제외한 모든 정점과 관계성이 있는 정점은 순위를 알 수 있는 것이고 하나의 정점이라도 관계성이 비어있는 정점이 있는 경우에는 순위를 알 수 없는 정점이 된다. 물론 핵심은 그 관계성을 어떻게 업데이트해주냐이다.
그래프는 키의 대소 관계로서 directed graph로 주어지긴 했지만 indegree, outdegree로 해서 양쪽 방향으로 이동은 가능하게 그래프의 정보를 가지고 있으면 가능할 것 같다는 생각이 든다. 그렇다면 모든 정점에서 한번씩 탐색을 해주는데 indegree방향으로는 인접한 정점끼리의 관계성만 보고 outdegree방향으로는 그 뒤의 정점들까지 더 탐색해가면서 다시 관계성을 업데이트 해주는 방식으로 접근했다. DFS로 접근하되 이미 들른 정점 체크를 해줄 수 없다는 것이 걱정이 됐으나 모든 정점이 대소관계를 가지므로 사이클이 생기지 않기도 하고 그 관계성을 계속해서 찾아가고 업데이트하는 것이 핵심이기에 적합하다고 판단했다.
#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]); } } }
그래프에서 정점 간의 최단거리를 구하는 알고리즘들이 다양하게 존재하는데 대표적인 것으로는 다익스트라, 벨먼포드 알고리즘이 있는데 두 알고리즘은 "한 정점에서 모든 정점까지의 최단거리"를 구하는 알고리즘이다. 하지만 현재 문제에서 요구하는 것은 거리의 값 자체가 중요한 것은 아니지만 거리로 표상되는 모든 정점 간의 관계성이고 "모든 정점에서 모든 정점까지의 최단거리"를 구하는 알고리즘인 플로이드-와샬 알고리즘을 적용할 수 있는 것이다.
알고리즘 자체에 대한 설명은 좋은 포스트 글들이 있이므로 링크로 남기도록 한다.
#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;
}