99클럽 코테 스터디 25일차 TIL / 순위(프로그래머스)

오늘의 학습 키워드

   - 알고리즘

   - 그래프 탐색

공부한 내용 본인의 언어로 정리하기

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

플로이드 와샬 알고리즘과 비슷한 형태로 푸는 문제였다

 

풀이 과정은 다음과 같다.

1. A가 B를 이긴다면 격자형 그래프에 graph[A][B] = 1, graph[B][A] = -1을 대입한다.

2. 이후 3중 반복문을 돌며 아래 로직을 수행한다.

2 - 1. 만약 i가 k를 이기면서, k가 j를 이긴다면

2 - 2. 이는 논리적으로 i는 j를 이길 수 있다.

2 - 3. 반대로 i가 k에게 지면서 k가 j에게 진다면

2 - 4. i는 j에게 진다고 볼 수 있다.

3. 위 내용을 반복문을 돌아가며 격자형 그래프에 채운다.

4. 마지막으로 반복문을 돌며 i를 기준으로 n - 1개 만큼의 순위가 정해졌다면 나의 순위를 알 수 있으므로 n - 1개인 경우 순위를 매길 수 있다고 볼 수 있다.

 

 

풀이는 다음과 같다.

class Solution {
    public int solution(int n, int[][] results) {
        
        int[][] graph = new int[n + 1][n + 1];
        
        for (int[] result : results) {
            graph[result[0]][result[1]] = 1;
            graph[result[1]][result[0]] = -1;
        }
        
        for (int k = 1; k <= n; k++) {
            
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    
                    if (graph[i][k] == 1 && graph[k][j] == 1) {
                        graph[i][j] = 1;
                        graph[j][i] = -1;
                    }
                    
                    else if (graph[i][k] == -1 && graph[k][j] == -1) {
                        graph[i][j] = -1;
                        graph[j][i] = 1;
                    }
                }
            }
        }
        
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int count = 1;
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] == 0) continue;
                else count++;
            }
            if (count == n) answer++;
        }
        
        
        
        return answer;
    }
}