[Swift 백준] 1389 케빈 베이컨의 6단계 법칙

풀이 아이디어

- 그래프 탐색 문제입니다.

- 트리형태가 아니고, 사이클이 일어날 수 있는 그래프이기 때문에 방문 체크에 유의해야 합니다.

- 각 노드까지의 거리를 담는 배열을 정의하여 bfs 함수 실행 후에 비교하여 최솟값을 찾아냅니다

 

 

풀이

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])

var graph: [[Int]] = Array(repeating: [], count: n + 1)

for _ in 0..<m {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let (a, b) = (input[0], input[1])
    //인접 그래프를 생성합니다
    graph[a].append(b)
    graph[b].append(a)
}

var minSum = Int.max
var answer = -1

func bfs(start: Int) -> Int {
    var isVisited = Array(repeating: false, count: n + 1)
    var distance = Array(repeating: 0, count: n + 1)
    var q = [start]
    isVisited[start] = true
    
    while !q.isEmpty {
        let current = q.removeFirst()
        
        for item in graph[current] {
            if !isVisited[item] {
                q.append(item)
                isVisited[item] = true
                distance[item] = distance[current] + 1
            }
        }
    }
    
    // 각 노드까지의 거리의 합을 return해줍니다
    return distance.reduce(0, +)
}

//반복문을 돌며 비교, 값을 대치해줍니다. 문제에서의 요구사항처럼 최솟값이 두번 이상 나와도 이후 값으로 변경되지않습니다.
for i in 1...n {
    let sum = bfs(start: i)
    if sum < minSum {
        minSum = sum
        answer = i
    }
}

print(answer)