SSAFY에서 플로이드 워셜을 배웠다.
모든 노드에서 다른 모든 노드까지 가는 경로 중 최단 거리를 계산하는 알고리즘이다.
이 알고리즘을 이해하기 위해 여러번 노력했지만 아직 완벽히 이해하지 않았다.
프로그래머스 순위 문제를 풀어보면서 다시 정리를 해보았고, 깨달은 바는 다음과 같다.
깨달은 바가 순위 문제를 그래프로 푸는 방식과 어떻게 연관되는지도 정리해본다.
1. 플로이드 워셜
1) 플로이드 워셜 알고리즘은 앞서 말했듯이 '모든 노드에서 다른 모든 노드까지 가는 경로 중 최단 거리를 계산하는 알고리즘이다.' 하지만 순위 문제와 접목해서 이 알고리즘을 이해하기 위해서는 이 알고리즘이 구하고자 하는 '최단거리'에 집중하기 보다 최단거리를 구하기 위해 동작하는 '과정'에 집중해야 하는 거 같다.
플로이드 워셜은 동적 프로그래밍 유형에 속한다. A번 노드에서 B번 노드까지 K번 노드를 경유해서 이동하는 것과, 직접 A에서 B로 이동하는 것을 비교해 더 짧은 거리를 테이블에 저장한다. 1 ~ N 번 노드가 있다면 순차적으로 1부터 N까지 모든 노드를 경유지에 대입하면서 갱신되는 값을 계속해서 누적하여 저장해 간다. 이렇게 누적해서 저장해갈 때 최단거리를 구할 수 있는 것은 동작 과정에서 A번 노드에서 B번 노드로 이동하는 '모든 가능한 경로를 고려하기 때문'으로 보인다.
손으로 플로이드 워셜의 동작 과정을 일일이 적어보니 노드가 1 ~ 4번까지 있다고 가정했을 때 4번에서 3번 노드로 가는 최단 거리는 K가 2일 때까지 해보면 정답이 나온다. K가 2일 때까지 4->3 번 노드의 최단거리를 구하기 위해 구한 경로는 다음과 같이 나온다.
4->3의 값을 구하기 위해 3, 4번을 경유하는 것은 없으므로 2번 경유지를 고려한 것이 최종 결과인데 이때 누적해서 고려한 경로를 확인해보면 결국 모든 경로를 고려해 본 것을 확인할 수 있다. 여기서 순위 문제를 푸는데 플로이드 워셜을 적용하기 위해서는 'A번 노드에서 B번 노드로 이동이 가능한가?'에 대해 플로이드 워셜이 알려줄 수 있는지를 확인해야 한다. 왜냐하면 결국 순위 문제는 각 선수의 승패를 확인하여 유향 그래프로 나타낼 수 있고, 이때 다른 노드를 거쳐서 특정 노드에 도달이 가능하다면 간접적으로 승패를 확인할 수 있으므로 앞선 질문에 가능하다는 답이 나오면 플로이드 워셜을 적용할 수 있을 것이다. 근데 이 질문은 생각보다 쉽게 대답이 가능하다. 모든 경로를 고려하여 최단 거리를 계속 갱신해나가는 과정에서 결국 플로이드 워셜은 A번 노드에서 B번 노드로 갈 수 있다는 것이 확인되면 그 경로 중에 최단 거리를 계속 갱신해주고 있기 때문이다. 결국 테이블에 거리 값이 초기에 설정한 무한대 값이 아닌 거리 값으로 저장되어 있다면 A번 노드와 B번 노드는 어떻게든 연결이 된다는 뜻이다. 따라서 순위문제에 적용이 가능하다.
2. 순위 문제는 그래프 문제
순위문제를 처음 봤을 때 '왜 이게 그래프 문제지?' 라고 생각했다. 구글링을 해서 해설을 보면서 깨달을 수 있었다.(https://nahwasa.com/85, 참고한 글) 각 선수를 노드라고 생각하고, 이기거나 지는 것으로 방향을 부여하면 승패 결과를 통해 그래프가 만들어 진다. A-B의 승패가 주어진 경우가 아니더라도 주어진 다른 승패결과를 통해 A-K-N...-B로 간접적인 연결이 가능하다면 A와 B의 승패를 확정할 수 있다.
따라서 이 문제는 플로이드 워셜이 아니라 BFS나 DFS로도 풀이가 가능하다. 그래프를 구성한 후에 A노드에서 B노드까지 이동이 가능한지 체크해보면 된다.
3.정답코드
- 플로이드 워셜 이용
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
int answer = n;
int[][] graph = new int[n+1][n+1];
for(int i=0; i<results.length; i++){
graph[results[i][0]][results[i][1]] = 1;
}
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(graph[i][k] + graph[k][j] == 2) graph[i][j] = 1;
}
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i==j) continue;
if(!(graph[i][j] == 1 || graph[j][i] == 1)){
--answer;
break;
}
}
}
return answer;
}
}- BFS 이용
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
int answer = n;
int[][] graph = new int[n+1][n+1];
for(int i=0; i<results.length; i++){
graph[results[i][0]][results[i][1]] = 1;
}
for(int i=1; i<=n; i++) {
boolean[] visited = new boolean[n+1];
Queue<Integer> q = new ArrayDeque();
q.add(i);
visited[i]= true;
while(!q.isEmpty()){
int cur = q.poll();
for(int j=1; j<=n; j++){
if(graph[cur][j] == 1 && !visited[j]){
graph[i][j] = 1;
visited[j] = true;
q.add(j);
}
}
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i==j) continue;
if(!(graph[i][j] == 1 || graph[j][i] == 1)){
--answer;
break;
}
}
}
return answer;
}
}