코딩테스트 연습 - 순위

집합으로 풀기

처음에 플로이드 와샬 알고리즘을 모를 때 푼 방법입니다.

문제 풀이 아이디어

문제의 조건에 의하면 기존에 주어진 경기 결과를 통해서 나머지 경기 결과를 유추할 수 있습니다. a 선수가 b 선수를 이겼다면 b 선수가 이긴 선수는 모두 a 선수가 이길 수 있습니다. 반대로 a 선수를 이긴 선수들은 모두 b 선수를 이길 수 있습니다. 즉 (a를 이긴 선수) > a > b > (b에게 진 선수)가 성립하는 것이지요.

따라서 주어진 results를 각각 선수 별로 이긴 선수와 진 선수를 리스트로 정리합니다. 리스트는 중복되는 경우를 방지하기 위해서 Array가 아니라 Set을 활용하겠습니다.

그리고 나서 각각의 선수 별로 (i 선수라고 하겠습니다.) i 선수를 이긴 선수들의 집합에 i 선수에게 진 선수들의 집합을 더합니다. 그리고 i 선수에게 진 선수들의 집합에 i 선수를 이긴 선수들의 집합을 더합니다. ( i를 이긴 선수 > i > i가 이긴 선수 )

이렇게 하면 주어진 result로 알 수 있는 각각의 선수가 이긴 선수와 진 선수가 모두 정해지게 됩니다. 이 때 모든 선수와의 승패관계가 정해진 선수를 세면 됩니다. 즉 이긴 선수 + 진 선수 == n - 1 (자신을 제외)인 선수들의 명수를 세면 됩니다.

코드

func solution(_ n: Int, _ results: [[Int]]) -> Int {
    
    // winners[i] = i에게 이긴 사람들
    var winners = Array(repeating: Set<Int>(), count: n + 1)
    // losers[i] = i에게 진 사람들
    var losers = Array(repeating: Set<Int>(), count: n + 1)
    
    for result in results {
        let winner = result[0]
        let loser = result[1]
        
        // loser에게 이긴 사람에 winner 추가
        winners[loser].insert(winner)
        // winner에게 진 사람에 loser 추가
        losers[winner].insert(loser)
    }
    
    for i in 1...n {
        // i를 이긴 모든 사람은 i가 이긴 모든 사람을 이긴다.
        for winner in winners[i] {
            losers[winner].formUnion(losers[i])
        }
        // i에게 진 모든 사람은 i를 이긴 모든 사람에게 진다.
        for loser in losers[i] {
            winners[loser].formUnion(winners[i])
        }
    }
    
    var ans = 0
    
    for i in 1...n {
        if winners[i].count + losers[i].count == n - 1 {
            ans += 1
        }
    }
    
    return ans
}

플로이드-와샬 알고리즘으로 풀이

플로이드 와샬 알고리즘이란?

플로이드-와샬 알고리즘이란 모든 정점 사이에 최단 경로를 찾는 알고리즘입니다. 간선에 가중치가 있는 그래프에서 주로 사용합니다.

간단하게 말하면 한 node에서 다른 node로 이동할 때 한방에(?) 가는게 빠른지 아니면 다른 node를 거쳐서 가는게 빠른지 따져보는 알고리즘이라고 보면 됩니다.

구현은 아주 간단합니다. 삼중반복문으로 구현하면 됩니다. ❗️ 거쳐가는 중간 node인 k가 가장 바깥쪽 반복문이어야 한다는 점에 주의합시다! (👉 이유: i를 가장 먼저 순회하면 다른 k로 인해 i → j의 최단 경로가 생겼을 때 그 경로 인해 단축된 경로가 반영되지 않음) 코드는 아래와 같습니다.

// i지점에서 k지점까지 가는데 k를 거쳐서 간다.
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
								// k를 거쳐서 가는 것이 더 빠르면 k를 거쳐서 가도록!
                if cost[i][j] > cost[i][k] + cost[k][i] {
                    cost[i][j] = cost[i][k] + cost[k][i]
                }
            }
        }
    }

문제 풀이 아이디어

그렇다면 이 문제에 어떻게 적용할 수 있을까요? 이 문제는 최단 경로와는 아무런 관계가 없어보이는데 말입니다. 이 문제와 플로이드 와샬 알고리즘의 접점은 바로 “거쳐서”라는 키워드입니다. 각각의 선수를 node라고 하고 시합의 결과를 간선이라고 하면 node와 node가 직접 연결되어 있는 것은 둘의 시합 결과가 results 안에 있는 것을 의미합니다.

반면에 이 문제의 조건에 따르면 두 선수의 직접적인 시합 결과가 없어도 다른 선수들과의 시합 결과를 통해 유추할 수 있습니다. 즉 node와 node가 직접 연결되어 있지 않아도 다른 선수를 “거쳐서” 가는 경로가 있을 수 있다는 것입니다.

따라서 플로이드 마샬 알고리즘을 통해서 구할 수 있는 모든 선수와 선수 사이의 경로 (= 시합 결과)를 구합니다. 그리고 모든 선수와 연결된 경로가 있는 선수를 세주면 됩니다.

코드

func solution(_ n:Int, _ results:[[Int]]) -> Int {
    
    // 시합 결과를 표현하기 위한 enum
    enum Result {
        case unknown, won, lost
    }
    
    // 시합 결과를 저장하는 경로
    var matrix: [[Result]] = Array(repeating: Array(repeating: .unknown, count: n + 1), count: n + 1)
    
    for result in results {
        let winner = result[0]
        let loser = result[1]
        matrix[winner][loser] = .won
        matrix[loser][winner] = .lost
    }
    
    // i 선수와 j 선수의 결과를 k 선수와의 결과를 통해서 유추한다.
    for k in 1...n {
        for i in 1...n {
            for j in 1...n {
                // i가 k를 이기는데 k가 j를 이긴다면, i가 j를 이긴다.
                if matrix[i][k] == .won && matrix[k][j] == .won {
                    matrix[i][j] = .won
                    matrix[j][i] = .lost
                // i가 k한테 지는데 k는 j한테 진다면, i는 j한테 진다.
                } else if matrix[i][k] == .lost && matrix[k][j] == .lost {
                    matrix[i][j] = .lost
                    matrix[j][i] = .won
                }
            }
        }
    }
    
    var ans = 0

    // i 선수의 모든 선수들과의 unknown이 아닌 경기 결과를 세서 n - 1이면 ans += 1
    for i in 1...n {
        var cnt = 0
        for j in 1...n {
            if matrix[i][j] != .unknown { cnt += 1 }
        }
        if cnt == n - 1 { ans += 1 }
    }

    return ans
}