백준 1697 숨박꼭질 - Swift

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

1697번: 숨바꼭질

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 

5 17

예제 출력 1 

4

 

풀이 방법

모든 경우의 수를 고려 해보는 것입니다.

5 에서 (5 + 1, 5 - 1, 5 * 2) 의 3가지 경우를 모두 탐색하고

6 에서 (6 + 1, 6 - 1, 6 * 2) 의 3가지 경우를 모두 이런 식으로 BFS를 실시합니다.

그러다가 17이 나오는 순간 멈추고 해당하는 노드의 깊이를 출력합니다.

참고로 DFS 말고 BFS를 하는 이유는 BFS는 최단 거리를 보장해주기 때문입니다. 쉽게 말해서 DFS는 17이 나오는 모든 경우의 수를 따져서 최단 거리를 비교해야 하는데 BFS는 처음으로 17이 나오는 순간이 최단 거리 이기 때문에  BFS가 적합합니다.

 

 

코드

let NM = readLine()!.split(separator: " ").map{ Int($0)! }
var max = Int(1e5) + 1 // 1000001 로 쓰는 것보다 빠름 40ms -> 12ms

func sol() {
    var index = 0
    var queue = [NM.first]
    var depth = [Int](repeating: max, count: max)
    depth[NM.first!] = 0
    
    while queue.count > index {
        let node = queue[index]!
        index += 1
        
        if node == NM.last! {
            print(depth[node])
            break
        }
        
        if node + 1 < max && depth[node + 1] == max {
            queue.append(node+1)
            depth[node + 1] = depth[node] + 1
        }
        
        if 0 <= node - 1 && depth[node - 1] == max {
            queue.append(node-1)
            depth[node - 1] = depth[node] + 1
        }
        
        if node * 2 < max && depth[node * 2] == max {
            queue.append(node*2)
            depth[node * 2] = depth[node] + 1
        }
    }
}

sol()

 

깨달은 점 

숫자 1000001 를 쓰는 것보다 Int(e5) + 1를 쓰면 알고리즘 속도에 도움이 된다.

쉽고 간단하게 속도를 올릴 수 있어서 자주 사용할 듯 싶습니다.