문제 링크 (opens new window)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

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

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

플러드필

숨바꼭질 5 문제에서는 플러드필 알고리즘이 적용된다. 문제의 중요한 지점이 동생의 1초 이후의 위치 변화를 언제 지정해주느냐인데, BFS의 경우 같은 깊이의 위치 탐색을 진행한 뒤에 다음으로 넘어가기 때문에 이에 대한 처리가 필요하다.

같은 뎁스 위치를 모두 탐색하기 위해서는 큐의 사이즈를 가져온 뒤 for문 탐색을 모두 마칠때까지 기다리는 방식으로 진행한다.

1차 풀이

1. 뎁스별 구분을 통해 적절한 시점에 가속 (2%에서 오답, 테스트케이스 17 5에서 오출력)

import Foundation

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

    var isEmpty: Bool {
        return count == 0
    }

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

    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]; var k = nk[1]
var acc = 1
var visited: [Int] = .init(repeating: 0, count: 500004)
var isFirst = true

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

while(!q.isEmpty && !flag) {

    let qSize = q.count

    for _ in 0..<qSize {
        guard let now = q.front else { break }
        _ = q.dequeue()

        if now == k {
            flag = true
            break
        }

        for next in [now + 1, now - 1, now * 2] {
            if next < 0 || next > 500000 || visited[next] != 0 {
                continue
            }

            visited[next] = visited[now] + 1
            q.enqueue(next)
        }
    }

    k += acc
    acc += 1
}

if flag {
    k -= (acc - 1)
    print(visited[k] - 1)
} else {
    print("-1")
}

2차 풀이

1. 8% 오답

let nk = readLine()!.split(separator: " ").map { Int($0)! }; let n = nk[0]; var k = nk[1]
var acc = 1
var visited: [Int] = .init(repeating: 0, count: 500004)
var isFirst = true
var ret = 0

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

while(!q.isEmpty && !flag) {

    let qSize = q.count

    for _ in 0..<qSize {
        guard let now = q.front else { break }
        _ = q.dequeue()

        if k > 500000 {
            break
        }

        if now == k {
            flag = true
            break
        }

        for next in [now + 1, now - 1, now * 2] {
            if next < 0 || next > 500000 || visited[next] != 0 {
                continue
            }

            if visited[k] != 0 && visited[k] < acc {
                if (acc - visited[k]) % 2 == 0 {
                    ret = visited[k] + acc - visited[k] - 1
                    flag = true
                    break
                }
            }

            visited[next] = visited[now] + 1
            q.enqueue(next)
        }
    }

    k += acc
    acc += 1
}

if ret != 0 {
    print(ret)
} else {
    if flag {
        k -= (acc - 1)
        print(visited[k] - 1)
    } else {
        print("-1")
    }
}

최종 풀이

1. 홀짝 구분 풀이

import Foundation

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

    var isEmpty: Bool {
        return count == 0
    }

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

    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]; var k = nk[1]
var acc = 1
var visited: [[Int]] = .init(repeating: .init(repeating: 0, count: 500004), count: 2)
visited[0][n] = 1
var flag = false

var q = Queue<Int>()
q.enqueue(n)

if n==k {
    _ = q.dequeue()
    flag = true
    acc = 0
}

while(!q.isEmpty) {
    k += acc

    if k > 500000 {
        break
    }

    if visited[acc % 2][k] != 0 {
        flag = true
        break
    }

    let qSize = q.count
    for _ in 0..<qSize {
        guard let now = q.front else { break }
        _ = q.dequeue()

        for next in [now - 1, now + 1, now * 2] {
            if next < 0 || next > 500000 || visited[acc % 2][next] != 0{
                continue
            }

            visited[acc % 2][next] = visited[(acc + 1) % 2][now] + 1

            if next == k {
                flag = true
                break
            }

            q.enqueue(next)
        }
        if flag { break }
    }

    if flag { break }
    acc += 1
}

if flag {
    print(acc)
} else {
    print("-1")
}