[99클럽] 99클럽 코테 스터디 25일차 TIL - 그래프 (Graph)

 

오늘의 문제

프로그래머스 - 순위 (출처 하단 표기)

 

문제

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

 

풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = n;
        
        Integer[][] result = new Integer[n+1][n+1]; // null로 초기화하기 위함
        for(int i=0; i<=n; i++) {
            result[i][i] = 0;   // 자신과는 경기 X
        }
        
        for(int i=0; i<results.length; i++) {
            for(int j=0; j<results[i].length; j++) {
                int win = results[i][0];
                int lose = results[i][1];
                
                result[win][lose] = 1;  // win이 lose에게 이겼을 때 1
                result[lose][win] = -1;  // lose가 win에게 졌을 때 -1
            }
        }
        
         for (int k=1; k<=n; k++) {
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) {
                    if (result[i][k] != null && result[k][j] != null && result[i][k] == 1 && result[k][j] == 1) {   // i가 k를 이기고 k가 j를 이기면 i는 j를 이김
                        result[i][j] = 1;
                        result[j][i] = -1;
                    }
                }
            }
        }

        // 배열의 행에서 null이 없으면 순위를 매길 수 있음
        for (int i=1; i<=n; i++) {
            boolean hasNull = false;
            for (int j=1; j<=n; j++) {
                if (result[i][j] == null) {
                    hasNull = true;
                    break;
                }
            }
            if (hasNull) answer--; // null이 포함된 행이 있으면 answer 감소
        }
        
        return answer;
    }
}

 

먼저 인접 행렬로 구성된 그래프를 만들어 승자와 패자의 점수를 계산하였다. 경기의 경우, a가 b에게 이기고 b가 c에게 이기면 a는 c에게 항상 이기게 된다. (a → b → c) 따라서 이를 계산하는 방법을 플로이드-워셜 알고리즘을 이용하여 구현하였다.

 

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 그래프에서 모든 쌍의 최단 경로를 계산하는 데 사용되며, 동적 프로그래밍을 기반으로 한다. 이 알고리즘은 음수 가중치를 허용하지만 음수 사이클이 있는 경우는 처리할 수 없다.
시간 복잡도 = O(n³)

// 플로이드-워셜 알고리즘
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // i에서 j로 가는 최단 경로를 k를 거쳐서 갱신
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }​

 

그래프를 Integer 배열로 선언했기 때문에 초기값이 null이 된다. 이를 무한대라고 가정한다면, a → b → c로 가는 최단 거리는 a가 c를 이길 때 승점을 1로 수정해야 한다는 말이다. result 배열에서 행이 null 값이 존재하면 순위를 매길 수 없다. 따라서 null이 포함된 행이 있는 경우 answer에서 값을 하나씩 빼는 과정으로 작성하였다.

 

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/49191