프로그래머스 - 순위 (Lv. 3)

문제 링크

풀이

import Foundation

func solution(_ n:Int, _ results:[[Int]]) -> Int {
    var mans = (0..<n).map { _ in Man() }
    
    // 경기 결과의 값들을 전부 대입한다.
    for result in results {
        let winManNum = result[0]
        let lossManNum = result[1]
        
        mans[winManNum - 1].weakMans.append(lossManNum)
        mans[lossManNum - 1].strongMans.append(winManNum)
    }
    
    BFS(&mans)
    
    var result = 0
    mans.forEach {
        // 확실히 나보다 강하거나 약한 남자들 전부 합한 값이 대회 인원 수라면 순위를 매길 수 있으니 통과
        if $0.strongMans.count + $0.weakMans.count == n - 1 {   
            result += 1
        }
    }
    
    return result
}

struct Man {
    var strongMans: [Int] = []  // 나보다 강한 남자들
    var weakMans: [Int] = []    // 나보다 약한 남자들
}

func BFS(_ mans: inout [Man]) {
    for index in 0..<mans.count {
        // 나보다 강한 남자들 체크
        var visite = Array(mans[index].strongMans)
        while visite.count > 0 {
            let nextIndex = visite.removeFirst() - 1
            for strongManIdx in mans[nextIndex].strongMans {
                if !mans[index].strongMans.contains(strongManIdx) {
                    mans[index].strongMans.append(strongManIdx)
                    visite.append(strongManIdx)
                }
            }
        }
        
        // 나보다 약한 남자들 체크
        visite = Array(mans[index].weakMans)
        while visite.count > 0 {
            let nextIndex = visite.removeFirst() - 1
            for weakManIdx in mans[nextIndex].weakMans {
                if !mans[index].weakMans.contains(weakManIdx) {
                    mans[index].weakMans.append(weakManIdx)
                    visite.append(weakManIdx)
                }
            }
        }
    }
}

후기

2중 BFS로 해결해보았습니다.
(강한 남자들 BFS로 전부 탐색 후, 약한 남자들도 BFS로 전부 탐색)
해결 방법만 알면 쉬운데 그 해결 방법을 고민하느라 시간이 오래 걸렸던 문제.