<Programmers> Graph, Floyd Warshall_순위 c++
5610 단어 GraphprogrammersalgorithmGraph
💡Summary & Idea
result
배열 각 행[a,b]
는a가 b를 이겼다
는 의미이다- 처음 각 선수간 순위가 있으니
위상정렬(Topological Sort)
로 구현해야 하나 생각을 했다 (indegree와 outdegree의 차수를 더한 값이 n-1이 되면 모든 선수들과 관계를 알 수 있으니 순위를 알 수 있지 않을까 했지만, 그렇지 않은 관계도 있었다) - 그래서 사용해야 하는 것이 모든 정점 쌍에 대해 둘 사이의 최단 거리를 찾는 플로이드 와샬 알고리즘을 사용한다
📜Floyd Warshall Algorithm
- 모든 정점 간 최단 거리를 구할 때 사용
- 정점 집합
S
에서u
에서v
로 가는 최단 경로의 길이를D(u,v)
라 할 때
① 경로가k
를 경유하지 않는다:S-{k}
에 포함된 정점들만을 경유점으로 사용
② 경로가k
를 경유한다:D(u,k)
와D(k,v)
로 경로를 나눌 수 있다
경유
③ 경유 지점k
는 정점 집합S
의 모든 값이 될 수 있다
④D(u,v)=min(D(u,v), D(u,k)+D(k,v))
로 나타낼 수 있다
- 플로이드 알고리즘에서 최단거리 계산하기
int V //정점의 개수 int adj[MAX_V][MAX_V] // adj[u][v]=u에서 v로 가는 간선의 가중치 int via[MAX_V][MAX_V] //via[u][v]=u에서 v까지 가는 최단 경로가 경유하는 점 중 가장 번호가 큰 정점 void floyd () { for (int i=0; i<V; i++) adj[i][j]=0; memset (via, -1, sizeof(via)); for (int k=0; k<V; k++) { for (int i=0; i<V; i++) { for (int j=0; j<V; j++) { if (adj[i][j]>adj[i][k]+adj[k][j]) { via[i][j]=k; adj[i][j]=adj[i][k]+adj[k][j]; } } } } } void reconstruct (int u, int v, vector<int> &path) { if (via[u][v]==-1) path.push_back(u); if (u!=v) path.push_back(v); } else { int w=via[u][v]; reconstrcut (u,w,path); path.pop_back(); //w가 중복으로 들어가므로 지움 reconstruct (w,v,path); } }
✏️Solution
vector<vector<bool>> adj
에서adj[u][v]=true
라는 뜻은 u가 v를 이긴다는 뜻이다- u가 k를 이기고 k가 v를 이기면 u가 v를 이기는 것과 같다
즉adj[u][k]==true && adj[k][v]==true
이면adj[u][v]=true
adj
를 조사해서 각 정점에서 경기 결과를 알 수 있는 경우가n-1
이면 모든 선수와 승/패를 판단할 수 있다는 뜻이므로 순위를 매길 수 있다는 뜻이다
✏️Source Code
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<vector<int>> results) {
int answer = 0;
vector<vector<bool>> adj(n+1, vector<bool> (n+1, false));
for (int i=0; i<results.size(); i++)
adj[results[i][0]][results[i][1]]=true;
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (i==j) continue;
if (adj[i][k] && adj[k][j])
adj[i][j]=true;
}
}
}
for (int i=1; i<=n; i++) {
int cnt=0;
for (int j=1; j<=n; j++) {
if (i==j) continue;
if (adj[i][j] || adj[j][i]) cnt++;
}
if (cnt==n-1) answer++;
}
return answer;
}
Author And Source
이 문제에 관하여(<Programmers> Graph, Floyd Warshall_순위 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Programmers-Graph-Floyd-Warshall순위-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)