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

문제 :

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

1389번: 케빈 베이컨의 6단계 법칙

 

분석 :

처음에는 왜 이게 BFS지 ? 깊이에 따라 내려가니까는 DFS 아닌가 싶었다. 하지만 다시 생각해보니 우리는 깊이가 낮은 친구 관계가 있다면 이 값을 반환해야 한다. 따라서 깊이가 낮은 곳에 원하는 원소가 있다면 visit를 true로 만들어 더 깊은 곳에 원하는 원소가 있어도 방문하지 않고 넘어갈수 있게된다.

 

또한 자기 자신을 제외한 모든 친구의 관계(깊이)를 알고 싶은 것으로 for문을 돌때 자기 자신의 깊이가 1인 친구가 아닌 1 ~ N까지 모두 검사해야 한다. 이 점을 참고하여 queue 인자에  queue(start: Int, find: Int, cnt: Int) 를 queue(start: Int, cnt: Int) 시작 원소만 업데이트 되게끔 수정하여 해결했다.

 

틀린 접근 코드 :

import Foundation
var line = readLine()!.split(separator: " ").map { Int(String($0))! }
var n = line[0]
var m = line[1]
var tree: [[Int]] = Array(repeating: [], count: n+1)
var visit: [Int] = Array(repeating: 0, count: n+1)

for _ in 0..<m {
    var l = readLine()!.split(separator: " ").map { Int(String($0))! }
    tree[l[0]].append(l[1])
    tree[l[1]].append(l[0])
}

func bfs_level(start: Int, find: Int, cnt: Int) {
    var queue = [(Int, Int, Int)]()
    visit[start] = 1
    queue.append((start, find, cnt))

    while !queue.isEmpty {
        let now = queue.first!.0
        let value = queue.first!.1
        let cn = queue.first!.2
        queue.removeFirst()
        
        if value > n { break }
        
        if tree[now].contains(value) {
            visit[value] = cn
            queue.append((start, value+1, 1))
            continue
        }

        for i in 0..<tree[now].count {
            var next = tree[now][i]

            if visit[next] == 0 {
                queue.append((next, value, cnt+1))
            }
        }
    }
}

 

Swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/04/17.
//

import Foundation
var line = readLine()!.split(separator: " ").map { Int(String($0))! }
var n = line[0]
var m = line[1]
var tree: [[Int]] = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)

for _ in 0..<m {
    let l = readLine()!.split(separator: " ").map { Int(String($0))! }
    tree[l[0]][l[1]] = 1
    tree[l[1]][l[0]] = 1
}


func bfs_level(start: Int, cnt: Int) -> Int {
    var visit: [Bool] = Array(repeating: false, count: n+1)
    var queue = [(Int, Int)]()
    var answer = 0
    visit[start] = true
    queue.append((start, cnt))
    
    while !queue.isEmpty {
        let now = queue.first!.0
        let cnt = queue.first!.1
        queue.removeFirst()
        
        for i in 1..<n+1 {
            if !visit[i] && tree[now][i] == 1 {
                answer += cnt
                queue.append((i, cnt + 1))
                visit[i] = true
            }
        }
    }
    
    return answer
}

var answer = 0
var min = 10000
for i in 1..<n {
    let temp = bfs_level(start: i, cnt: 1)
    if(temp < min) {
        min = temp
        answer = i
    }
}
print(answer)