(알고리즘 스터디) 15주차 금_Graph📈_(Programmers) 순위

🌟 프로그래머스 / Graph / Level 3 / 순위

📃 문제

프로그래머스

🚫 제한 사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

👀 입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

🤔 풀이 방법

1️⃣ 내 생각 정리 

➡️ 아래 2가지 방법을 생각해보았지만 코드로 옮기거나 논리적 구상이 어려웠다. 따라서 다른 블로그 글을 참고하여 문제를 해결하였다.

 

① 배열을 활용

➡️ 경기 결과에 따라 선수들의 배열 인덱스를 바꿔나가면서 순위를 확인하고자 했다. 그러나 이 방법은 코드로 구현이 불가능 했다.

② depth 를 활용

➡️ 방향 그래프를 생성하여 가장 깊은 depth 를 구해 활용해보고자 했다. 그러나 이 방법은 접근 방식 자제가 잘못되었다.

2️⃣ Floyd-Warshall 알고리즘

➡️ 플로이드-워셜 (Floyd-Warshall) 알고리즘이 이 문제를 푸는 대표적인 방법이라고 나와있었다.

 

① Floyd-Warshall Algorithm 이란?

➡️ 방향성 가중치 그래프에서 "최단거리"를 찾는 것을 목적으로 하는 알고리즘이다. 최단거리를 구하는 대표적인 알고리즘으로는 "다익스트라" 도 있는데, 다익스트라의 경우 한 정점으로부터의 최단 거리를 구하지만 플로이드-워셜 알고리즘의 경우 모든 정점으로부터의 최단 거리를 구한다는 점에서 차이가 있다고 한다.

 

② Floyd-Warshall Algorithm 의 논리

➡️ 위 그림에서 정점 A 에서 정점 C 로 가는 방법은 ①G[A, C] = 8 과 ② G[A,B] + G[B,C] = 2+3 = 5 가 있다. 두 방법 모두 C 로 갈 수 있지만, 값은 B를 거쳐서 가는 방법이 더 효율적이기 때문에 더 작은 값인 5를 저장하게 된다.

 

③ Floyd-Warshall Algorithm 구현

// Pseudo Code
let dist be a 
procedure FloydWarshallWithPathReconstruction() is
    // 초기화
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
        prev[u][v] ← u
    for each vertex v do
        dist[v][v] ← 0
        prev[v][v] ← v
    // 본격적인 Floyd-Washall 수행
    for k from 1 to |V| do
        for i from 1 to |V|
            for j from 1 to |V| // 중간값들을 계속 확인하면서 min 값으로 대체
                if dist[i][j] > dist[i][k] + dist[k][j] then
                    dist[i][j] ← dist[i][k] + dist[k][j]
                    prev[i][j] ← prev[k][j]

3️⃣ 풀이적용 (Floyd-Warshall Algorithm)

➡️ 해당문제는 가중치 그래프의 형태는 아니기 때문에 완전히 플로이드-워셜 알고리즘에 부합하다고 할 수는 없다. 하지만 해당 문제의 요점은 경기결과를 알 수 없는 것들을 결과가 알려진 경기들을 통해서 알 수 있느냐이다.

예시) [1, 4], [4, 5]
제한 상황) 실력 차이는 절대적이다.
➡️ 1번 선수가 4번 선수를 이겼고, 4번 선수는 5번 선수를 이긴 상황이다.
➡️ 1번 & 5번 선수의 경기 결과는 알려지지 않았지만 위 상황을 바탕으로 1번 선수가 5번 선수를 이겼을 거라는 추론이 가능하다.

➡️ 따라서 이 문제는 플로이드-워셜의 일반적인 코드에서 min 값을 비교하는 것이 아닌, 중간값 결과가 존재하는지를 확인하는 것으로 변형을 해주면 된다.

// 플로이드-워셜 변형

for (int k=0; k<n; k++) {
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (i == j) continue;
            if (result[i][k] == 1 && result[k][j] == 1) {
                result[i][j] = 1;
            }
        }
    }
}

4️⃣ 결과 확인

➡️ 모든 테스트 코드에서 잘 돌아갔다.

💻 풀이 코드

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        // 결과를 담기 위한 인접행렬
        int[][] result = new int[n][n];
        
        // results 배열값 담기
        for (int[] r : results) {
            result[r[0]-1][r[1]-1] = 1;
        }
        
        // Floyd-Warshall Algorithm 적용 (변형 ver)
        // 중간 노드를 반복문의 처음에 배치
        for (int k=0; k<n; k++) {
            for (int i=0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    if (i == j) continue;
                    if (result[i][k] == 1 && result[k][j] == 1) {
                        result[i][j] = 1;
                    }
                }
            }
        }
        
        int cnt = 0;
        
        // 순위 확정 선수 수 도출
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                if (i==j) continue;
                if (result[i][j] == 1 || result[j][i] == 1) cnt++;
            }
            // 결과를 아는 경기 수가 전체 선수의 수-1 과 같으면 순위 확정
            // ex) 선수가 5명인 경우 한 선수에 대해 4경기에 대한 결과를 모두 알아야 순위 확정
            if (cnt == n-1) answer++;
            cnt=0;
        }
        
        return answer;
    }
}

🤔 궁금한 점

➡️ 맨처음 Floyd-Warshall 을 공부하고 적용시켜보았을 때 반복문을 도는 순서 때문에 테스트 케이스에 통과하지 못하는 경우들이 있었다. 코드를 확인해보니 도는 순서가 중간 노드 > 시작 노드  > 도착 노드 였다. 찾아보니 거쳐가는 노드를 하나씩 확인하는 것이므로 중간 노드를 맨 앞에 두는 것 같았는데 솔직히 아직 논리적으로 해당 순서가 지켜져야하는지는 이해하지 못했다.