문제 출처

코딩테스트 연습 > 그래프 > 순위
https://school.programmers.co.kr/learn/courses/30/lessons/49191

문제 설명

선수의 수 n, 경기 결과 2차원 배열 results 가 주어질 때, 정확하게 순위를 매길 수 있는 선수의 수를 return 하라.

2차원 배열 results의 요소 [a,b] 는 a는 b에게 승리했다. 라는 뜻이다.

접근 방법

이 문제는 플로이드 워셜 알고리즘을 이용해야한다.

플로이드 워셜 알고리즘은 간단하게
i->k->j 경로가 i -> j 경로보다 더 짧다면 갱신하는 알고리즘으로
모든 노드 간 거리 정보 갱신하기 위해 사용한다.
추가로 기존 노드의 정보를 바탕으로 다음 노드 정보를 알고 싶을 때도, 사용된다.

3중 for문을 이용하여 출발과 도착 사이에 중간 경유지를 확인하여 만약 출발과 도착 사이에 중간 경유지가 있다면 출발과 도착을 잇는다.

이후 graph를 확인하며 graph[i]에 연결 된 요소가 총 n-1개이면 answer를 증가시킨다.

class Solution {
    public int solution(int n, int[][] results) {
        int[][] graph = new int[n+1][n+1];
        for(int[] edge : results){
            graph[edge[0]][edge[1]] = 1;
            graph[edge[1]][edge[0]] = -1;
        }
        
        // 출발
        for(int i = 1; i <=n; i++){
            // 도착
            for(int j = 1; j <= n; j++){
                // 중간 경유
                for(int k = 1; k <= n; k++){
                    if(graph[i][k] == 1 && graph[k][j] == 1){
                        graph[i][j] = 1;
                        graph[j][i] = -1;
                    }
                    if(graph[i][k]== -1 && graph[k][j] == -1){
                        graph[i][j] = -1;
                        graph[j][i] = 1;
                    }
                }
            }
        }
        int answer = 0;
        
        for(int i = 0; i <= n; i++){
            int count = 0;
            for (int j = 0; j <= n; j++){
                if(graph[i][j] != 0) count++;
            }
            if(count == n-1) answer++;
        }
        return answer;
    }
}

Review

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int[][] graph = new int[n+1][n+1];
        int answer = 0;
        // 그래프 생성(이기면 1, 지면 -1)
        for(int i = 0; i<results.length; i++){
            graph[results[i][0]][results[i][1]] = 1;
            graph[results[i][1]][results[i][0]] = -1;
        }
        // 시작
        for(int i =1; i<=n; i++){
            // 끝
            for(int j = 1; j<=n; j++){
                // 중간 경유
                for(int k = 1; k<=n; k++){
                    if(graph[i][k] == 1 && graph[k][j] == 1){
                        graph[i][j] = 1;
                        graph[j][i] = -1;
                    }
                    
                    if(graph[i][k] == -1 && graph[k][j] == -1){
                        graph[i][j] = -1;
                        graph[j][i] =1;
                    }
                }
            }
        }
        
        for(int i = 1; i<=n; i++){
            int count = 0;
            for(int j = 1; j<=n; j++){
                if(graph[i][j] != 0 ) count++;
            }
            if(count == (n-1)) answer++;
        }
            
        return answer;
    }
}

알게된 점

플로이드 워셜 알고리즘은 최소 경로를 구할 때, 혹은 기존 노드를 바탕으로 확장적으로 다음 노드 정보를 알고 싶을 때 사용된 다는 것을 알았다.

문제푼 흔적

Review