[프로그래머스] 49191 순위

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

🔍  해결 과정

이 문제는 그래프 문제 중에서도 플로이드 워셜 알고리즘을 통해 해결할 수 있습니다.

문제의 예시를 바탕으로 그래프를 그려보면 다음과 같습니다.

그림에서 화살표가 나가는 노드가 승리한 노드임을 의미하고, 화살표가 들어가는 노드가 패배한 노드임을 의미합니다. 

2번 노드는 모든 연결된 모든 노드와의 승패 정보를 알 수가 있고, 5번 노드는 2번 노드와 연결된 다른 노드들과의 승패 관계를 바탕으로 5위임을 알 수가 있어 결론적으로 순위를 알 수 있는 노드의 개수는 2개입니다.

 

위 그래프 그림을 테이블 정보로 나타내면 다음과 같이 나타낼 수가 있습니다.

그림에서 각 행에 있는 노드가 모든 열의 노드에서의 승패 결과를 나타내면 위 그림과 같습니다.

이 때 모든 선수와의 승패 결과를 알기 위해서 플로이드 워셜이 적용 됩니다. 즉,

선수 A가 선수 B를 이기고, 선수 B가 선수 C를 이기면, 선수 A는 선수 C를 이긴 것으로 간주합니다.

이 원리를 바탕으로 플로이드 워셜을 적용하여 graph 테이블을 정리하면 다음과 같습니다.

 

행에서 2번 노드와 5번 노드를 봤을 때 모든 노드와의 승패 정보를 알 수가 있고, 나머지 노드는 그렇지 않기에 순위를 알 수 있는 노드는 총 2개임을 알 수가 있습니다.

---

✏️ 코드

import java.util.*;

class Solution {
    
    private static final int WIN = 1;
    private static final int LOSE = -1;
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] graph = new int[n + 1][n + 1];
        
        // 승패 정보를 graph에 기록하기
        for (int[] result : results) {
            int win = result[0];
            int lose = result[1];
            
            graph[win][lose] = WIN;
            graph[lose][win] = LOSE;
        }
        
        //플로이드 워셜 알고리즘 적용하기
        for (int k = 1; k <= n; ++k) {
            for (int i = 1; i <= n; ++i) {
                if (graph[i][k] == 0) {
                    continue;
                }
                
                for (int j = 1; j <= n; ++j) {
                    if (graph[j][k] == 0) {
                        continue;
                    }
                    
                    if (graph[i][k] == graph[k][j]) {
                        graph[i][j] = graph[k][j];
                    }
                }
            }
        }
        
                
        // 알 수 있는 순위 정보 출력하기
        for (int i = 1; i <= n; ++i) {
            int zero = 0;
            
            for (int j = 1; j <= n; ++j) {
                if (graph[i][j] == 0) {
                    ++zero;
                }
            }
            
            if (zero == 1) {
                ++answer;
            }
        }
        
        return answer;
    }
}