백준 - 효율적인 해킹 (1325)

let fIO = FileIO()
let N = fIO.readInt()
let M = fIO.readInt()
var graph: [[Int]] = Array(repeating: [], count: N + 1)
var visited = Array(repeating: false, count: N + 1)
var score = Array(repeating: 0, count: N + 1)
var maxScore = 0
var answer = ""

// 그래프 만들기
for _ in 0..<M {
    let a = fIO.readInt()
    let b = fIO.readInt()
    graph[a].append(b)
}

// 신뢰도 계산
for node in 1...N {
    visited = Array(repeating: false, count: N + 1)
    dfs(node)
}

for i in 1...N {
    if score[i] == maxScore {
        answer += "\(i) "
    }
}

print(answer)

func dfs(_ node: Int) {
    visited[node] = true
    
    for vertex in graph[node] {
        if !visited[vertex] {
            score[vertex] += 1
            maxScore = max(maxScore, score[vertex])
            dfs(vertex)
        }
    }
}

신뢰하는 관계가 A B 라는 것은 A가 B를 신뢰한다는 뜻이며, 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는 신뢰를 가장 많이 받는 컴퓨터이다.

→ 모든 노드마다 BFS / DFS 알고리즘을 적용하며 신뢰도를 업데이트 한 후 가장 높은 신뢰도를 가진 정점의 번호를 출력한다.

결과는 시간 초과.. (스위프트 && 백준이 또..) 시간 초과를 해결하지 못한 분들이 많은 것 같아서 일단 패스..