[Algorithm] 순위

[hwangJi-dev]

💬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/49191

💬 Idea

• 이기는 경우를 탐색할 수 있는 winGraph와, 지는 경우를 탐색할 수 있는 loseGraph를 각각 만든다.
• 1부터 N까지 각각 winGraph, loseGraph를 탐색하며 이긴 경우와 진 경우의 탐색 결과를 도출한다.
• 이긴 경우와 진 경우의 탐색 결과를 합쳤을 때 1부터 N까지의 숫자가 모두 포함된다면 순위를 알 수 있는 선수라는 아이디어를 떠올려
  Set 자료구조를 활용하여 Set(win + lose).count == n 이라면 결과값에 +1을 해주었다.

💬 풀이

import Foundation

func solution(n:Int, results:[[Int]]) -> Int {
    var loseGraph: [Int: [Int]] = [:]
    var winGraph: [Int: [Int]] = [:]
    var ans = 0
    
    for i in results {
        if loseGraph[i[1]] == nil {
            loseGraph[i[1]] = [i[0]]
        } else {
            loseGraph[i[1]]?.append(i[0])
        }
        
        if winGraph[i[0]] == nil {
            winGraph[i[0]] = [i[1]]
        } else {
            winGraph[i[0]]?.append(i[1])
        }
    }
    
    func dfs(_ isWin: Bool, _ start: Int) -> [Int] {
        var visitedQueue: [Int] = []
        var neetToVisitStack: [Int] = [start]
        
        while !neetToVisitStack.isEmpty {
            let node = neetToVisitStack.removeLast()
            
            if visitedQueue.contains(node) { continue }
            visitedQueue.append(node)
            
            if isWin {
                neetToVisitStack += winGraph[node] ?? []
            } else {
                neetToVisitStack += loseGraph[node] ?? []
            }
        }
        
        return visitedQueue
    }
    
    for i in 1...n {
        let win = dfs(true, i)
        let lose = dfs(false, i)
        
        if Set(win + lose).count == n {
            ans += 1
        }
    }
    
    return ans
}