[Algorithm] 효율적인 해킹

[hwangJi-dev]

💬 문제

https://www.acmicpc.net/problem/1325

💬 Idea

• B를 해킹하면 A를 해킹할 수 있으므로, B만 그래프에 정점으로 저장해준 후 B를 돌며 최대 해킹 수를 구한다.
• 시간초과 줄여보겠다구,, 노력했는데!!! 이 문제는 Swift 언어로 풀이하면 어느 풀이든 시간초과가 나는 문제라고 한다. (readLine 입력 때문인 것 같다네용)

💬 풀이

import Foundation

func solution1325() {
    let MN = readLine()!.split(separator: " ").map({ Int($0)! })
    var graph: [Int: [Int]] = [:]
    
    for _ in 1...MN[1] {
        let nodes = readLine()!.split(separator: " ").map({ Int($0)! })

        if graph[nodes[1]] == nil {
            graph[nodes[1]] = [nodes[0]]
        } else {
            graph[nodes[1]]?.append(nodes[0])
        }
    }
    
    func dfs(graph: [Int: [Int]], start: Int, visited: [Int]) -> [Int] {
        var visited = visited
        
        if let nodes = graph[start] {
            for i in nodes {
                if !visited.contains(i) {
                    visited.append(i)
                    visited = dfs(graph: graph, start: i, visited: visited)
                }
            }
        }
        
        return visited
    }
    
    var hackingCountArr: [Int] = [Int](repeating: 0, count: MN[0] + 1)
    
    for i in graph.keys {
        let res = dfs(graph: graph, start: i, visited: []).count
        hackingCountArr[i] = res
    }
    
    let maxCnt = hackingCountArr.max()
    
    for (idx, i) in hackingCountArr.enumerated() {
        if i == maxCnt {
            print(idx)
        }
    }
}