[Swift][BFS] 백준 13549번 (숨바꼭질3)

요구능력 : BFS에 대한 이해

 

코드설명 : 

 

이전단계 문제인 숨바꼭질을 풀고오면 수월하게 풀리는문제이다. 먼저 풀고오는걸 권장하는게아닌 먼저풀고오는게 맞는거같다.

 

큐에 삽입한다는 말은 움직인다는 말인데, 움직이면 시간계산을 해줘야하므로 움직이는것과 시간계산을 함께 넣어서 큐를 튜플배열로 사용하였다.

순간이동이라는 조건이 추가되서 1초가아닌 0초를 더해야하는것을 제외하고는 숨바꼭질과 문제가 똑같다.

queue에서 튜플의 첫번째 요소는 현재 위치, 두번째 요소는 걸리는 시간이다.

 

후기 : BFS관련 복잡한 문제들을 몇번봐서 이렇게 간단한건 어느정도 풀만한 수준이 된거같다.

let nk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nk[0]
let k = nk[1]
var queue: [(Int, Int)] = []
var visited = Array(repeating: false, count: 100001)
bfs()
func bfs(){
    queue.append((n, 0))
    
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        if pop.0 == k {
            print(pop.1)
            break
        }
        if pop.0 * 2 < 100001 && !visited[pop.0 * 2]{
            visited[pop.0 * 2] = true
            queue.append((pop.0 * 2, pop.1))
        }
        
        if pop.0 - 1 >= 0 && !visited[pop.0 - 1]{
            visited[pop.0 - 1] = true
            queue.append((pop.0 - 1, pop.1 + 1))
        }
        
        if pop.0 + 1 < 100001 && !visited[pop.0 + 1]{
            visited[pop.0 + 1] = true
            queue.append((pop.0 + 1, pop.1 + 1))
        }
        
        
    }
}