[swift] 백준 - 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는 정수이다.

출력

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

예제

---

성공 풀이

import Foundation

let NK = readLine()!.split { $0 == " " }.map { Int($0)! }, N = NK[0], K = NK[1]
var queue = [(N,0)]
var visited = Array(repeating: false, count: 100001)

while true {
    let now = queue.removeFirst()
    if now.0 == K {
        print(now.1)
        break
    }
    [now.0+1, now.0-1, now.0*2].forEach {
        if $0>=0 && $0<=100000 && !visited[$0] {
            queue.append(($0,now.1+1))
            visited[$0] = true
        }
    }
}

풀이 키워드

• 문제를 읽어보니 DP로 푸는 문제인가 싶었는데.. 알고리즘 분류를 보니 그래프탐색으로 분류되어 있어, 바로 너비우선탐색(BFS)으로 풀었습니다.
• 첫 풀이 코드에선 방문체크하는 배열 visited를 Set으로 만들어 방문체크를 했었습니다. Set의 contains() 함수는 시간복잡도가 O(1)인 걸로 알고 있어서 시간초과가 안 날 거라고 생각했는데요.. 네 맞습니다 사실 contains의 잘못이 아니고.. 점의 최댓값에 따라 10만 위는 제외했어야 했는데 인지하지 못했습니다.
• Set의 잘못이라 생각하고 false값을 가진 배열 10만1개를 만들어 방문처리를 했습니다. 두 번째 풀이에서는 점의 위치가 0보다 이상이고 10만보다 이하라는 조건을 추가해서 시간초과를 면할 수 있었습니다.