[Level 3 / 그래프] 순위 + Swift

문제 링크

코딩테스트 연습 - 순위

문제

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

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

입력

let n = 5
let results = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

출력

2

문제 풀이

func solution(_ n:Int, _ results:[[Int]]) -> Int {
    var answer = 0
    var db: [[Bool]] = Array(repeating: Array(repeating: false, count: n+1), count: n+1)
    
    // 이긴 승부만 true로 저장
    for result in results {
        db[result[0]][result[1]] = true
    }
    
    // i가 k를 이기고, k가 j를 이겼다면 i가 j를 이긴 것임
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
                if db[i][k] && db[k][j] { db[i][j] = true }
            }
        }
    }
    
    // i의 순위를 알기 위해선 자신을 제외한 모든 승패를 알아야 함
    for i in 1...n {
        var count = 0
        for j in 1...n {
            if db[i][j] || db[j][i] { count += 1 }
        }
        if (count >= n-1) { answer += 1 }
    }
    
    return answer
}