[Swift] 백준_숨바꼭질

문제

 

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

1697번: 숨바꼭질

 

 

풀이

 

BFS를 이용해 하나의 수에서 -1한 값, +1한 값, *2한 값을 각각 조건을 확인해준 후, 큐에 넣고 확인하는 것을 반복해주었다.

 

100001크기의 배열을 선언해서 구현하였따.

처음에 수빈이가 있는 queue[5]를 0으로 초기화하고, +1, -1, *2한 값들에 대해서 배열의 해당 위치가 -1인지 확인 후에 아니라면 이전 값에 +1을 하여 queue[target]이 -1이 아닐때 바로 queue[target]을 출력하도록하였다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var count = [Int](repeating: -1, count: 100001)
let target = input[1]
var queue = [input[0]]
var idx = 0
count[input[0]] = 0
while count[target] == -1 {
    let current = queue[idx]
    idx += 1
    let temp = [current + 1, current - 1, current * 2]
    for i in temp {
        if i < 0 || i > 100000 {
            continue
        }
        if count[i] == -1 {
            count[i] = count[current] + 1
            queue.append(i)
        }
    }
}
print(count[target])

 

___________________________________________________________________________________________________

 

BFS가 응용이 정말 많이 돼서 빨리 익숙해져야한다.