백준 - 케빈 베이컨의 6단계 법칙 (1389)

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, M) = (input[0], input[1])

var distance = Array(repeating: Array(repeating: 1000000, count: N+1), count: N+1)

// 인접 행렬 만들기
for _ in 0..<M {
    let input = readLine()!.split(separator: " ").map { Int(String($0))! }
    distance[input[0]][input[1]] = 1
    distance[input[1]][input[0]] = 1
}

// 자기 자신은 0
for i in 1...N {
    distance[i][i] = 0
}

// 플로이드 와샬 알고리즘 실행
for k in 1...N {
    for i in 1...N {
        for j in 1...N {
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
        }
    }
}

// 케빈 베이컨 수 가장 작은 사람 찾기
var answer = 1
var minValue = Int.max

for i in 1...N {
    let nowValue = distance[i].reduce(0, +)
    if minValue > nowValue {
        minValue = nowValue
        answer = i
    }
}

print(answer)

BFS로도 풀 수 있지만 N의 크기가 작기 때문에 플로이드 와샬 알고리즘을 사용할 수도 있다.

처음 인접 행렬을 만들 때 친구 관계가 존재하는 경우 가중치는 1로 업데이트 한다. 이때 양방향 모두 업데이트 해야 한다.