[프로그래머스] 순위

https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

2021-08-30

---

class Solution {
    public int solution(int n, int[][] results) {
         int answer = n;
        int[][] dist = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) continue;
                dist[i][j] = 987654321;
            }
        }
 
        for(int i = 0; i < results.length; i++) {
            dist[results[i][0]-1][results[i][1]-1] = 1;
        }
 
       for(int m = 0; m < n; m++) {
           for(int s = 0; s < n; s++) {
               for(int e = 0; e < n; e++) {
                   if(dist[s][e] > dist[s][m] + dist[m][e]) {
                       dist[s][e] = dist[s][m] + dist[m][e];
                   }
               }
           }
       }
 
       for(int i = 0; i < n; i++) {
           for(int j = 0; j < n; j++) {
               if(dist[i][j] == 987654321 && dist[j][i] == 987654321) {
                   answer--;
                   break;
               }
           }
       }
 
        return answer;
    }
}

#문제풀이

이 문제는 도저히 감이 안 잡혀서, 결국 다른 사람 풀이 검색해서 참고했다...

 

결론을 말하면 플로이드 와샬을 이용해서 풀면 되는 문제인데, 정말 생각하지도 못했던 부분이었다.

 

예를 들어, 우리가 [1, 2]의 경기 결과를 알고, [2, 3]의 경기 결과를 알고 있다면 그 의미는 [1, 3]의 경기 결과도 알 수 있다는 의미이다. 그리고 플로이드 와샬은 모든 정점에서 (+거쳐가는) 모든 정점으로까지의 최단 경로를 구할 수 있는 알고리즘이다. 

그래서 이 알고리즘을 사용하면 최단 경로와 거쳐가는 경로들을 모두 알 수 있다. 즉, [1, 2]와 [2, 3]이 주어졌을 때 [1, 3]도 알 수 있는 것이다.

 

일반적으로 플로이드 와샬 사용하는 방식 그대로 dist 배열 초기화 하고, 모든 정점과 거쳐가는 정점까지 체크해서 dist 배열을 업데이트 시켜줬다.

 

그리고, 맨 마지막에 만약 dist 경로 [i][j]와 [j][i]의 경로가 모두 INF라면(갱신이 되지 않았다면), 그 경로는 아에 없다라는 뜻이다. 즉, 이 문제로 따지면 승패를 알 수가 없다.

 

나를 제외한 남은 정점들을 방문할 수 있어야지 승패를 알 수 있다.

 

---

비슷한 문제라고 어떤 블로그에서 봤는데, 나중에 풀어봐야겠다.

https://www.acmicpc.net/problem/10159

10159번: 저울