[프로그래머스/Lv. 2] 순위 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        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 = 0 ; k <= n ; k++) {
            for(int i = 0 ; i <= n ; i++) {
                for(int j = 0 ; j <= n ; j++) {
                    if(graph[i][k] == 1 && graph[k][j] == 1) {  // 간접적으로 이길 경우의 수 : i → k, k → j라면, i → j
                       graph[i][j] = 1;
                    }
                }
            }
        }
        
        for(int i = 1 ; i <= n ; i++) {
            int cnt = 0;    // 지고 이긴 경우의 수 (= 0이 아닌 값)
            
            for(int j = 1 ; j <= n ; j++) {
                if(graph[i][j] == 1 || graph[j][i] == 1) { // 두 선수 간 승부 결과 파악이 가능한 경우
                    cnt++;
                }
            }
            
            if(cnt == n - 1)    // 선수 순위 확정 가능한 경우
                answer++;
        }
        
        return answer;
    }
}

 

 

🧩 해결 아이디어

• 플로이드-워셜 ; 모든 정점에서 다른 모든 정점으로의 최단 거리 계산.

- 여기서 최단 거리까지는 계산할 필요 없고, 도달 가능한지만 확인하면 됨

 

 

---

🔺 다른 풀이들

- 두 선수 A B 간 승부 결과를 1과 -1로 표현하셨다. (1 : A가 이김 / -1 : B가 이김)

그림 과정 설명도 복습할 때 봐야겠다.

[프로그래머스] 순위 (Java)

 

---

💬 느낀 점

플로이드 워셜은 DP 기법을 활용한 알고리즘...

그래프 문제라고 해서 DFS랑 BFS 쓸 생각만 했었는데...

분발하자!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스] 순위-JAVA

 

[프로그래머스] 순위 - Java