[Swift][BFS] 백준 1697번 (숨바꼭질)

요구능력 : BFS에 대한 이해

 

코드설명 : 

 

왜 BFS로 풀어야되는지에 대한 설명이 아주 잘나와있다.https://chanhuiseok.github.io/posts/baek-14/ 

[백준] 1697번 - 숨바꼭질

 

스위프트의 경우에는 큐를 구현해줘야하기 때문에 필요한 부분만 구현해줬다.

BFS의 경우 처음에 큐가 비어있기 때문에 큐에 입력받은 수를 푸쉬해준다.

그리고 큐에서 데이터를 하나 꺼내오고 꺼내온 데이터가 k와 같다면 while문을 빠져나가준다.

while문의 조건을 true로 놔둬도 상관없다. 문제풀이이기 때문에, data가 k와 같지않은 경우는 없기때문이다.

 

아래의 세 가지 경우를 모두 돌면서

1) x - 1

2) x + 1

3) 2 *x

 

1. 방문한 노드를 큐에 넣어준다.

 

2. 또 다시 방문할 필요가 없기 때문에, 방문처리를 해준다.

또 다시 방문하면 횟수만 늘어나는 것이기 때문에,, 

 

3. 몇 초 걸렸는지 depth배열을 이용해서 저장한다.

depth배열은 미리 10001까지 0이 선언 해놨다.

5 17예제로 설명해주면,

코드를 읽어보면 알겠지만, 처음 돌때 depth[5] = 0 이라서 depth[5]의 자식 노드들인 4, 6, 10은 각각 depth에 1을 갖게 된다.

depth = 1은 1초가 걸렸다는 의미이다.

이걸 while문으로 depth += 1로 해주면 편리하지만, 시간초과가 나서 이렇게 배열로 처리하였다.

 

 

후기 : BFS문제는 아직 어렵다 .. 처음에 log(n^2)으로 풀었는데, 계속 시간초과가 되길래 문제를 다시 읽어보니 100000까지 데이터가 입력되던거였다.. 그래서 log(n)으로 풀기위해 depth를 따로 배열로 만들었다.

struct Queue{
    var que: [Int] = []
    mutating func push(_ x: Int) {
        que.append(x)
    }
    mutating func pop() -> Int {
        que.reverse()
        if let a = que.popLast() {
            que.reverse()
            return a
        }
        return 0
    }
    func empty() -> Bool {
        return que.isEmpty
    }
    func size() -> Int{
        return que.count
    }
}

func bfs(_ n: Int, _ k: Int) -> Int {
    var queue = Queue()
    queue.push(n)

    while !queue.empty() {
        let data = queue.pop()
        if data == k {
            break
        }
        if data > 0 && !visited[data - 1] {
            queue.push(data - 1)
            visited[data - 1] = true
            depth[data - 1] = depth[data] + 1
        }
        if data < 100000 && !visited[data + 1] {
            queue.push(data + 1)
            visited[data + 1] = true
            depth[data + 1] = depth[data] + 1
        }
        if data * 2 < 100001 && !visited[2 * data] {
            queue.push(2 * data)
            visited[2 * data] = true
            depth[data * 2] = depth[data] + 1
        }
    }
    return depth[k]
}


let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = arr[0]
let k = arr[1]
var visited: [Bool] = Array(repeating: false, count: 100001)
var depth: [Int] = Array(repeating: 0, count: 100001)
let result = bfs(n, k)
print(result)