오늘 풀어볼 문제는
프로그래머스의 순위로,
플로이드-와샬 알고리즘(Floyd-Warshall algorithm)을 변형하여 접근하는 풀이입니다.
하여 먼저 플로이드-와샬 알고리즘에 대해 접근해보도록 하겠습니다.
🔎 플로이드-와샬 알고리즘(Floyd-Warshall algorithm)이란?
플로이드-와샬 알고리즘(Floyd-Warshall algorithm)은 그래프 이론에서 모든 정점 간의 최단 경로를 찾는 알고리즘입니다.
이 알고리즘은 음의 가중치를 가지는 그래프에서도 사용할 수 있습니다.
특히, 음의 사이클이 없는 그래프에서 모든 정점 사이의 최단 경로를 찾는 데 사용됩니다.
이 알고리즘의 주요 아이디어는 "거쳐가는 정점"을 고려하여 더 나은 경로가 있는지를 검사하는 것입니다.
모든 정점 쌍에 대한 최단 경로를 찾기 위해 3중 중첩된 반복문을 사용합니다.
알고리즘의 동작은 다음과 같습니다:
📍 동작원리
1. 초기 그래프의 인접 행렬을 구성합니다.
여기서 각 (i, j) 쌍에 대한 값은 정점 i에서 정점 j까지의 직접 가중치입니다.
이때, 인접하지 않는 정점 쌍의 경우 무한대로 설정합니다.
int[][] graph = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
2. 모든 정점 쌍 (i, j)에 대해 다음 작업을 수행합니다.
3. 각 정점 k를 거쳐가는 경로를 고려하여, 정점 i에서 정점 j로 가는 최단 경로를 업데이트합니다.
즉, 현재까지 알려진 i에서 j로의 최단 경로와 i에서 k를 거쳐 j로 가는 경로를 비교하여 최단 경로를 갱신합니다.
위의 과정을 반복하여 모든 정점 쌍에 대한 최단 경로를 찾습니다.
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}예제 코드로 보면 아래와 같습니다.
import java.util.Arrays;
public class FloydWarshall {
static final int INF = 99999;
public static void main(String[] args) {
// 1. 초기 그래프의 인접 행렬을 구성합니다.
int[][] graph = {
{0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0}
};
int[][] shortestPaths = floydWarshall(graph);
System.out.println("모든 정점 쌍 간의 최단 경로:");
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph.length; j++) {
if (shortestPaths[i][j] == INF) {
System.out.print("INF ");
} else {
System.out.print(shortestPaths[i][j] + " ");
}
}
System.out.println();
}
}
// 2. 모든 정점 쌍 (i, j)에 대해 다음 작업을 수행합니다.
public static int[][] floydWarshall(int[][] graph) {
int V = graph.length;
int[][] dist = new int[V][V];
// 그래프의 값을 가지고 초기화
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 플로이드-와샬 알고리즘 적용
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// 3. 각 정점 k를 거쳐가는 경로를 고려하여, 정점 i에서 정점 j로 가는 최단 경로를 업데이트합니다.
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
}
이 알고리즘의 시간 복잡도는 O(V^3)이며, 여기서 V는 그래프의 정점 수입니다.
따라서 이 알고리즘은 작은 규모의 그래프부터 중간 규모의 그래프까지 효율적으로 작동합니다.
그러나 매우 큰 그래프에 대해서는 성능이 떨어질 수 있습니다.
📍 동적 프로그래밍적인 측면
참고로, 플로이드-와샬 알고리즘은 동적 프로그래밍적인 측면으로도 볼 수 있니다.
그 이유는 정점 쌍 간의 최단 경로는 작은 부분 문제들의 최단 경로를 결합하여 얻을 수 있기 때문입니다.
📍 다익스트라 알고리즘과의 차이점
다익스트라 알고리즘이 하나의 정점에서 다른 모든 정점으로의 최단 경로를 구한다면,
플로이드-와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구합니다.
다익스트라 알고리즘이 가장 적은 비용을 하나씩 선택했다면,
플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 수행합니다.
프로그래머스의 순위 문제는 승리 및 패배한 결과를 바탕으로 선수들 간의 순위를 결정해야 하는 문제입니다.
이 문제는 위에서 설명한 플로이드-와샬 알고리즘의 변형으로, 차이점은 다음과 같습니다.
🔎 변형 요소
1) 그래프 구성
일반적인 플로이드-와샬 알고리즘에서는 그래프의 가중치가 각 간선의 길이입니다.
하지만 이 문제에서는 각 경기 결과에 따라 선수들 간의 관계를 표현하는 방식으로 그래프를 구성했습니다.
예를 들어, A 선수가 B 선수를 이겼다면 (A, B) 간선의 가중치는 1로, 반대로 B 선수가 A 선수를 이겼다면 -1로 설정됩니다.
2) 경로 탐색
플로이드-와샬 알고리즘에서는 모든 정점 쌍 간의 최단 경로를 찾는 것이 목표입니다.
하지만 이 문제에서는 주어진 경기 결과를 바탕으로 선수들 간의 관계를 업데이트하여 최종적으로 각 선수의 순위를 결정합니다.
따라서 경로 탐색과 동적 프로그래밍의 측면에서 일부 변형이 있습니다.
3) 경로 업데이트
플로이드-와샬 알고리즘에서는 거쳐가는 정점을 고려하여 최단 경로를 업데이트합니다
이 문제에서는 선수들 간의 경기 결과를 통해 선수들 간의 관계를 업데이트합니다.
위와 같은 변형은 주어진 문제의 특성에 따라 필요한 변형이며,
일반적인 플로이드-와샬 알고리즘과 유사한 접근 방식을 가지고 있습니다.
코드로 이해하면 아래와 같습니다.
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
int[][] match = new int[n][n];
// 1) 그래프 구성
for(int[] result : results){
int winner = result[0] - 1;
int loser = result[1] - 1;
match[winner][loser] = 1; // win
match[loser][winner] = -1; // lose
}
// 2) 경로 탐색
// a->b 이고 b->c이면 a->c 인 경우
for(int b=0; b<n; b++) {
for(int a=0; a<n; a++) {
// 진 경우는 제외
if(match[a][b] <= 0) {
continue;
}
// 이긴 경우 (a->b)
for(int c=0; c<n; c++) {
// 3) 경로 업데이트
// b->c인 경우, 그리고 a와 c의 관계를 알 수 없는 경우
if(match[b][c] > 0 && match[a][c] == 0) {
match[a][c] = 1;
match[c][a] = -1;
}
}
}
}
for(int i=0; i<match.length; i++) {
int cnt = 0;
for(int j=0; j<match[i].length; j++) {
if(match[i][j] != 0) cnt++;
}
// n에서 자기 자신을 제외하고 (-1) 값이 있는 경우 순위를 알 수 있음.
if(cnt == n - 1) answer++;
}
return answer;
}
}1) 선수들의 이기고 지는 경우를 그래프화 하고,
2)3) 플로이드-와샬 알고리즘을 변형하여 이기고 지는 경우를 추가적으로 알 수 있는 경우를 그래프에 업데이트 했습니다.
플로이드-와샬 알고리즘이 모든 정점 쌍 간의 최단 경로를 구하는 것이 목표라면,
주어진 문제는 업데이트된 그래프를 바탕으로 경로를 가지는 경우를 구하는 것이 목적인 문제였습니다.
이상 플로이드-와샬 알고리즘을 통해 접근하는 순위 풀이 였습니다.
더 좋은 방법이 있다면 언제든 피드백 환영합니다 :)
