첫 풀이

• 적당한 케이스만 고려해서 완전탐색 방식으로 구현
• 3%에서 오답

import Foundation

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

// 같은 시간대에는 세가지 경우만
var visited: [Bool] = .init(repeating: false, count: 100000)
var time = Int.max
var ret = 0

// 동생 찾았을때 Time값이 infinite가 아니면 이미 찾은 상태였으므로 값 비교 후 재귀 완전종료
// ret + 1 여부는 time값 최소 여부에 따라 결정
func go(_ here: Int, _ depth: Int) {
    if here > 100000 {
        return
    }

    // 동생 위치 찾았을때
    if here == k {
        // 동생 위치를 처음 찾았을때
        if time == Int.max {
            time = depth
            ret = 1
        } else {
            if time > depth {
                // 동생 위치를 다른 방법으로 이미 찾은 상태인데 지금의 방법이 더 빠른 방법일때
                time = depth
                ret += 1
            } else {
                // 동생 위치를 다른 방법으로 찾았는데 지금 방법이 더 느린 경우 그냥 리턴
                return
            }
        }
    }

    // 못찾았을때
    // 1. 동생 위치보다 오른쪽인 경우
    // X-1만 해야해서, 왼쪽으로 depth + 간격만큼 이동했을때 이미 찾은 최소 시간을 벗어나면 안됨
    // 다른 곳에서 동생 이미 찾았을때

    if here > k {
        if time != Int.max && here - k + depth <= time {
//            print("RIGHT: \(time), 간격: \(here - k) new time: \(here - k + depth)")
            time = here - k + depth
//            ret += here - k + depth
            ret += 1
            return
        } else if here - k + depth > time{
            return
        }

        // 동생 아직 못찾은 상태이면서 1번 상태일때
        if time == Int.max {
//            print("depth: \(depth), here: \(here) k: \(k)")
            time = depth + here - k - 1
//            ret = depth + here - k
            ret += 1
            return
        }
    }

    // 2. 동생 위치보다 왼쪽인 경우
    // X+1 & 2*X 위치 둘다 검증해봐야됨
    if here < k && time > depth && !visited[depth]  {
        visited[depth] = true
        go(here * 2, depth + 1)
        go(here - 1, depth + 1)
        go(here + 1, depth + 1)
    }
}

go(n, 0)

print(time)
print(ret)

풀이

1. BFS 풀이
2. 자잘한 반례가 너무 많았음 (최소최대 신경쓰기, n == k일때 신경쓰기)

import Foundation

struct Queue<T> {
    var head = 0
    var array: [T?] = []

    var count: Int {
        return array.count - head
    }

    var isEmpty: Bool {
        return count == 0
    }

    mutating func enqueue(_ element: T){
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

let nk = readLine()!.split(separator: " ").map { Int($0)! }; let n = nk[0]; let k = nk[1]
var q = Queue<Int>()
q.enqueue(n)
var ret: [Int] = .init(repeating: 0, count: 100004)
var visited: [Int] = .init(repeating: 0, count: 100004)
visited[n] = 1
ret[n] = 1

while(!q.isEmpty) {
    guard let now = q.front else { break }
    _ = q.dequeue()

    for next in [now - 1, now + 1, now * 2] {

        if next < 0 || next > 100000 {
            continue
        }

        if visited[next] == 0 {
            visited[next] = visited[now] + 1
            ret[next] += ret[now]
            q.enqueue(next)
        } else {
            if visited[next] == visited[now] + 1 {
                ret[next] += ret[now]
            }
        }
    }
}
if n == k {
    print(0)
    print(1)
} else {
    print(visited[k] - 1)
    print(ret[k])
}

재풀이

import Foundation

struct Queue<T> {
    var head = 0
    var array: [T?] = []

    var count: Int {
        return array.count - head
    }

    var isEmpty: Bool {
        return count == 0
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

let nk = readLine()!.split(separator: " ").map { Int($0)! }; let n = nk[0]; let k = nk[1]
var visited: [Int] = .init(repeating: 0, count: 200004) // 두배 고려
var short: [Int] = .init(repeating: 0, count: 200004)

var q = Queue<Int>()
q.enqueue(n)
visited[n] = 1
short[n] = 1

while(!q.isEmpty) {
    guard let current = q.front else { break }
    _ = q.dequeue()

    for next in [current + 1, current - 1, current * 2] {
        if next < 0 || next > 100000 {
            continue
        }

        if visited[next] == 0 {
            visited[next] = visited[current] + 1
            short[next] += short[current]
            q.enqueue(next)
        } else {
            if visited[next] == visited[current] + 1 {
                short[next] += short[current]
            }
        }
    }
}

print(visited[k] - 1)
print(short[k])