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

요구능력 : BFS에 대한 이해

 

코드설명 : 

 

"이게틀려?" 를 많이 시전한 문제이다.

 

이 문제를 풀기전에 숨바꼭질부터 풀고오자.

숨바꼭질에서 달라진점은 지나온경로를 찾는것이다.

지나온경로는 코드에서 visited배열에 저장해줬다.

방문처리와 동시에 경로를 저장했다. 이렇게 안해주고 배열을 따로 추가하면 메모리초과가난다.

경로추가하는 부분은 아래 주석처리를 해두었다.

 

 

 

1. 메모리초과

=> 크기가 100001인 배열 3개를 만들어서 메모리초과가 났다.

=> 아, 참고로 경로를 찾기위한 배열(아래코드에선 visited)에 초기값을 0으로 세팅하면 당연히 메모리 초과가 난다.

=> 이유는 2 * x에 0이들어가면 0인걸 참고하면 된다.

 

2. 컴파일에러

처음에 n을 방문처리해줬는데, 방문처리를 하면 코드가 꼬이게 됬다.

방문처리를 해주려면 어떤 수를 넣어야하는데 visited[n] = 0 처럼 넣어줘버리면,

아래 주석달아놓은데서 컴파일에러가 발생한다.

예를들어서 1 1을 입력했다고 가정하면,

visited[1] = 0이된다.

그럼 visited[0] = - 1인 값이 idx에 들어가게되서 index에러가 나는것이다.

 

방문처리를 안해줘도 초기값이 -1이기 때문에 위와같은 상황이 발생한다.

 

그래서 n과 k가 같은 경우를 따로 if문으로 잡아준것이다.

 

visited가 bool값을 받았으면 방문처리를 해놔도 상관없었지만, 이번건 방문처리를 해놓으면 값이 꼬이게되는 것이었다.

그리고 애초에 방문처리를 할 필요가 없는게, 만약 n과 같은 수가 돌고돌아서 나오더라도 그 수가 나온곳은 가장 빠를 수가 없기때문에 배제가된다. 방문처리를 해놓으면 약간의 시간이득을 보긴하지만, 리스크를 감수하면서까지의 이득은 아닌거같다.

 

후기 : 메모리초과와, 컴파일에러가 매우 많이 났다.

알고보면 참 당연한부분을.. 헤맸..다.

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

struct Queue{
    var queue: [Int] = []

    mutating func push(_ x: Int){
        queue.append(x)
    }
    mutating func pop() -> Int{
        queue.reverse()
        let a = queue.popLast()!
        queue.reverse()
        return a
    }
    mutating func empty()-> Bool{
        return queue.isEmpty
    }

}


func bfs() -> Int{
    var queue = Queue()
    queue.push(n)
    while true{
        let x = queue.pop()

        if x == k {
            return depth[x]
        }
        if x > 0 && visited[x - 1] == -1 {
            visited[x - 1] = x //이전 경로추가
            queue.push(x - 1)
            depth[x - 1] = depth[x] + 1
            
        }
        if x < 100000 && visited[x + 1] == -1{
            visited[x + 1] = x //이전 경로추가
            queue.push(x + 1)
            depth[x + 1] = depth[x] + 1
            
        }

        if 2 * x <= 100000 && visited[2 * x] == -1{
            visited[2 * x] = x //이전 경로추가
            queue.push(2 * x)
            depth[2 * x] = depth[x] + 1

        }

    }

}
if n == k{
    print(0)
    print(n)
}else{
    print(bfs())
    var idx = visited[k]
    while idx != n {//입력받은 값 방문처리 시, 컴파일에러
        result.append(idx)
        idx = visited[idx]
    }
    result.append(n)
    if n != k {
        result.reverse()
        result.append(k)
        
    }
    print(result.map{String($0)}.joined(separator: " "))

}