[백준] 숨바꼭질 (1697)

문제 설명

백준 1697번 문제 링크

입력 및 출력

» 입력

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

» 출력

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

예제 입출력(테스트케이스)

입력	출력
5 17	4

문제 힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

문제 풀이(SWIFT) 1

//
//  main.swift
//  BOJ1697_SWIFT
//
//  Created by choiyoujun on 2022/03/11.
//

let NK = readLine()!.split(separator: " ").map { Int($0)! }
var check = [Bool](repeating: false, count: 100_001)
let N = NK[0]
let K = NK[1]
var ans = 0
var q = [(next: Int, sec: Int)]()

if N == K {
    print(0)
} else {
    check[N] = true
    q.append((N, 0))
    
    while !q.isEmpty {
        let now = q.removeFirst()
        if now.next == K {
            print(now.sec)
            break
        }
        
        if (0..<100_001).contains(now.next * 2) && !check[now.next * 2] {
            q.append((now.next * 2, now.sec + 1))
            check[now.next * 2] = true
        }
        
        if (0..<100_001).contains(now.next - 1) && !check[now.next - 1] {
            q.append((now.next - 1, now.sec + 1))
            check[now.next - 1] = true
        }
        
        if (0..<100_001).contains(now.next + 1) && !check[now.next + 1] {
            q.append((now.next + 1, now.sec + 1))
            check[now.next + 1] = true
        }
        
    }
}

문제 풀이(SWIFT) 2

//
//  main.swift
//  BOJ1697_SWIFT
//
//  Created by choiyoujun on 2022/03/11.
//

func search() {
    var q = [(0, n)]
    var left = 0
    var check = [Bool](repeating: false, count: 100_001)
    
    while left < q.count {
        let (sec, current) = q[left]
        if current == k {
            print(sec)
            break
        }
        
        for next in [current - 1, current + 1, current * 2] {
            if next >= 0 && next <= 100_000 && !check[next] {
                q.append((sec + 1, next))
                check[next] = true
            }
        }
        
        left += 1
    }
}

let nk = readLine()!.split(separator: " ").map { Int($0)! }
let (n, k) = (nk[0], nk[1])
search()