[알고리즘] Swift -백준 #1697(숨바꼭질) -BFS

문제링크

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는 정수이다.

출력

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

 

---

분석

수빈이는 걷거나 순간이동을 할 수 있다.

걷는 것 = x위치에서 1초 후 x-1 또는 x+1 로 이동

순간이동 = x위치에서 1초 후 2*x 로 이동

수빈이와 동생의 위치가 주어졌을 때 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하시오

가장 빠른 방법을 구하는 것이므로 BFS를 사용하자

 

풀이 과정

n = 수빈이의 위치, k = 동생의 위치

걷는 것과 순간이동의 계산을 이용해서 k값이 될 수 있는 방법을 찾는다.

처음에 위치가 5일 때 수빈이가 다음으로 갈 수 있는 위치는 4, 6, 10이다.
그 다음으로 갈 수 있는 위치는 3, 5, 8, 7, 12, 9, 11, 20 이다.
해당 위치에서 방문한 적이 없는 곳에서 가지치기를 한다.
한 번 이동할 때마다 1초씩 증가한다.
위치가 17이되면 종료한다.

 

풀이

class Queue<T> {
    var enQueue: [T]
    var deQueue: [T] = []

    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        self.enQueue = queue
    }
    
    func push(_ element: T) {
        enQueue.append(element)
    }
    
    func pop() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
}

let input = readLine()!.split(separator: " ").map{ Int($0)!}
let n = input[0] //수빈이 위치
let k = input[1] //동생의 위치

let MAX = 100000
var checkArr = Array(repeating: false, count: MAX+1)
var arr = Array(repeating: 0, count: MAX+1)

func isValid(_ n: Int) -> Bool {
    return 0 <= n && n <= MAX ? true : false
}

func bfs(_ n: Int, _ k: Int) {
    checkArr[n] = true
    
    let q = Queue([Int]())
    q.push(n)
    
    while !q.isEmpty {
        let pop = q.pop()
        if pop == k {
            print(arr[pop])
            break
        }
        if isValid(pop-1) && !checkArr[pop-1] {
            checkArr[pop-1] = true
            q.push(pop-1)
            arr[pop-1] = arr[pop]+1
        }
        if isValid(pop+1) && !checkArr[pop+1] {
            checkArr[pop+1] = true
            q.push(pop+1)
            arr[pop+1] = arr[pop]+1
        }
        if isValid(pop*2) && !checkArr[pop*2] {
            checkArr[pop*2] = true
            q.push(pop*2)
            arr[pop*2] = arr[pop]+1
        }
    }
}

bfs(n, k)

 

결과

 

 

---

📂  정리

처음에는 왼쪽 코드로 진행했는 데 런타임에러가 났다.

진짜 별짓을 다해봤는데 안되고 진짜 스트레스 받아서 포기하려고 했는데 자주 묻는 질문에 나와 같은 문제를 겪은 사람이 있어서 해결할 수 있었다 ㅜ

 

런타임에러가 나는 이유는 배열의 크기에 대한 문제가 가장 크다.

해당 문제는 배열에 대한 범위체크를 한 후에 방문체크를 해줘야하는 데

왼쪽 코드는 범위체크를 후에 해줬기 때문에 에러가 난 것이다.

 

범위체크를 먼저 하자!!