순위 : https://programmers.co.kr/learn/courses/30/lessons/49191
Problems
Solves
다익스트라 알고리즘을 공부하다보니 다익스트라와 유사한 유형인 플로이드 와샬 알고리즘을 알게되었다. 바로 알아보도록 하자.
다익스트라와 플로이드 와샬 둘 다 최단 거리를 구하는 알고리즘이라는 공통점을 가지고 있지만, 다익스트라는 하나의 정점에서 출발했을때 다른 모든 정점으로의 최단거리를 구하는 알고리즘이고 플로이드 와샬은 모든정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다.
여기서 플로이드 와샬의 특징이자 핵심은 거쳐가는 다른 정점을 기준으로 최단거리를 구하는 것이다.
간단하게 플로이드 와샬의 개념을 집고 넘어가본다.
위의 그림과 같은 그래프가 있다고 가정해보자. 각각의 노드들은 방향성을 가지며 다른 노드들과 연결되어있다.
각 노드들의 가중치를 나타낸 배열로 나타내면 위와 같다. 자기자신을 가리키는 노드는 없으니 graph[i][i]는 0이다.
플로이드 와샬은 거쳐가는 다른 정점을 기준으로 최단거리를 구한다고 했다. 그렇기 때문에 A노드에서 B노드로의 최단거리를 구할때 C노드를 거쳐서 간 경우의 거리를 비교해서 최단거리일때 가중치값을 갱신해준다.
graph[A][B] > graph[A][C]+graph[C][B]일때 graph[A][B] = graph[A][C]+graph[C][B]로 갱신을 해주면 되는것이다.
위 그래프를 플로이드 와샬 알고리즘을 통해 최단거리를 구하는 과정에서 노드1을 거칠때의 상태변화를 보면
graph[2][4] = graph[2][1]+graph[1][4]로 갱신되었고 graph[3][2] = graph[3][1]+graph[1][2]로 갱신된것을 확인할수 있다.
이렇게 모든 과정을 수행하고 나면 아래와 같은 결과가 나오게 된다.
이는 모든 노드에서 모든 노드로의 최단거리를 나타내는 배열인셈이다.
그렇다면 이제 문제를 확인해보자
처음에 봤을때 이게 어딜봐서 플로이드 와샬 알고리즘을 사용하지? 라는 생각을 했었는데, 다른 분의 풀이를 보면서 이해할수 있었다.
문제의 핵심은 A선수가 B선수를 이겼다면 A선수는 B선수를 항상 이긴다. 이거인것 같다.
그리고 문제에서 경기 결과를 분실했다고 했고 여기서 플로이드 와샬 알고리즘을 적용해보자면, A와 B간의 결과를 모른다. 그런데 A와 C간의 결과를 알고 C와 B간의 결과를 안다면 A와 B의 결과를 알수 있는것이다.
이겼을때 1, 모를때 0, 졌을때 -1로 두고 보았을 때 grade[A][C]==1 && grade[C][B]==1이라면 A가 C를 이기고, C가 B를 이긴것이기 때문에 A가 이긴 C를 B는 진다는 것이다.
그렇기 때문에 grade[A][B]=1, grade[B][A]=-1 이 되게 되는것이다.
이를 반복해서 나온 결과값에서 자신을 제외한 모든 선수와의 결과가 0이 아닌 수가 되었을 경우 순위를 알수있게 된다.
Code
class Solution {
int[][] grade;
int N;
public int solution(int n, int[][] results) {
//선수간의 결과 배열
//1 = 승, -1 = 패, 0 = 모름
//ex) grade[1][2] = 1 : 1번 선수가 2번선수에게 승
grade = new int[n+1][n+1];
for(int i=0;i<results.length;i++){
int winner = results[i][0];
int losser = results[i][1];
grade[winner][losser] = 1;
grade[losser][winner] = -1;
}
//k : 거쳐가는 선수
for(int k = 1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
//k선수를 거쳐서 비교했을때 i가 k를 이기고 k가 j를 이기면 i가 j를 이김
if(grade[i][k]==1 && grade[k][j]==1){
grade[i][j]=1;
grade[j][i]=-1;
}
//k선수를 거쳐서 비교했을때 i가 k에게 지고 k가 j에게 지면 j가 i를 이김
if(grade[i][k]==-1 && grade[k][j]==-1){
grade[i][j]=-1;
grade[j][i]=1;
}
}
}
}
//자기자신을 제외한 선수와의 결과가 0이 아니면 승부를 알수있음.
int answer=0;
for(int i=1;i<=n;i++){
int count=0;
for(int j=1;j<=n;j++){
if(grade[i][j]==0){
count++;
}
}
if(count==1) answer++;
}
return answer;
}
}Result
플로이드 와샬이라는 알고리즘의 개념과 다익스트라, 플로이드 와샬의 차이를 공부할수 있었다.
몇 일 뒤에 카카오에서 낸 문제 풀어봐야지
Reference
