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

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

 

BFS

점 N에서 K까지 이동하는데, -1,+1, *2 로 이동할 수 있다고 할 때 K까지 가장 빠르게 도착할 수 있는 시간 출력하기

 

접근방법

이 문제는 숨바꼭질 2랑 아주 비슷한 문제다.

차이점은 -1,+1만큼 이동할 때는 1초가 걸리지만 *2 만큼 이동할 때는 순간이동이라 0초가 걸린다는 것

그리고 가장 빨리 도착한 시간과 경우의 수를 출력하는 게아니라 가장 빨리 도착한 시간만 출력해주면 된다는 거

그래서 숨바꼭질 2 코드에서 *2 하는 경우에서 nowdist+1을 대입하는게 아니라 nowdist를 그대로 대입해주었고,

경우의 수를 계산하는 코드를 지워서 제출했다.

 

뭔가 숨바꼭질4는 경우의 수 세라는 문제일 것 같긴한데

 

소스코드

 

import Foundation

func solution() {
    let input:[Int] = (readLine()?.split(separator: " ").map { Int($0)! })!
    let n:Int = input[0]
    let k:Int = input[1]
    
    var dist:[Int] = [Int](repeating: Int.max, count: 100001)
    var cnt:[Int] = [Int](repeating: 0, count: 100001)
    
    dist[n] = 0
    cnt[n] = 1
    
    var q:[Int] = []
    q.append(n)
    
    while !q.isEmpty {
        let now = q.removeFirst()
        let nowdist = dist[now]
        
        if now-1 >= 0 && now-1 <= 100000 {
            if dist[now-1] > nowdist+1 {
                // 처음방문
                dist[now-1] = nowdist+1
                cnt[now-1] = cnt[now]
                q.append(now-1)
            } 
        }
        if now+1 <= 100000 && now+1 >= 0 {
            if dist[now+1] > nowdist+1 {
                // 처음방문
                dist[now+1] = nowdist+1
                cnt[now+1] = cnt[now]
                q.append(now+1)
            }
        }
        if now*2 <= 100000 && now*2 >= 0 {
            if dist[now*2] > nowdist {
                // 처음방문
                dist[now*2] = nowdist
                cnt[now*2] = cnt[now]
                q.append(now*2)
            }
        }
    }
    
    print(dist[k])
}

solution()