[Swift][BFS] 백준 16954번 (움직이는 미로 탈출)

요구능력

BFS와 level별로 BFS를 확인할 수 있는지

 

문제풀이

접근법은 뭔가 대놓고 BFS이다.

처음 접근할때 다들 접근법이 가지각색일 것같다.

 

이 문제는 시간이라는 요소가 정말 중요한 문제이다.

이 문제를 풀기전에 3차원 배열에 대해 간단히 짚고 넘어가야한다.

우선, 3차원 배열은 arr[][][]이렇게 표현하는데 arr[면][행][열]로 보면된다.

이 문제에서는 면은 시간으로 볼것이다.

 

시간별로 행열의 방문여부를 확인하는 이유는 중복을 없애기 위함이다.

벽의 위치가 같을 때 같은지점을 중복해서 방문하면 시간낭비만 되는 비효율적인 코드가 된다.

벽은 시간에 따라서 움직인다.

따라서 시간에 따라 방문할 수 있는 위치도 초기화해줘야 한다.

그래야 자기자신의 위치에도 중복없이 방문이 가능하다.

 

나름 중요한 요소중에 하나라고 생각하는 벽옮기기이다.

나는 벽을 reversed를 이용하여 O(1)의 시간복잡도로 벽을 움직였다.

이 벽의 경우 BFS특성상 큐가 벽을 가지고다니도록 관리하였다.

func down(_ arr: [[String]]) -> [[String]]{
    var temp = Array(arr.reversed()).dropFirst()
    temp.append([".",".",".",".",".",".",".","."])
    return Array(temp.reversed())
}

 

큐는 시간, x좌표, y좌표, 벽의위치를 담은 2차원 String배열로 구성하였다.

이 문제는 어차피 8초이후로는 벽에 부딪힐 수가 없다. 벽이 모두 아래로 내려가서 사라지기 때문이다.

그래서 처음에 3차원배열(visited)에서 면의 개수를 9개로 지정한 것이다.

우리는 지금 0초부터 시작해서 8초까지 본것이다.

8초에는 queue의 위치가 어디에 있던지간에  x==0 && y ==7에 만족할 수 있다.

visited[8][0][0]의 위치에 있더라도 visited[8][0][7]까지 도달이 가능하다는 것이다.

이유는? 벽이없기때문에

따라서 nt의 경우 계속해서 증가시켜서 굳이 성능을 저하시킬 필요없이 nt = (t + 1, 8)까지 시간을 8초로 제한을 두는 가지치기를 한것이다.

func bfs(){
    var queue = [(Int, Int, Int, [[String]])]()
    var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 8), count: 8), count: 9)
    let copiedArr = arr
    queue.append((0, 7, 0, copiedArr))
    visited[0][7][0] = true

    var idx = 0
    while queue.count > idx {
        let (t, x, y, tempArr) = queue[idx]
        idx += 1

        if x == 0 && y == 7{
            result = true
        }

        for i in 0..<9{
            let nx = x + dx[i]
            let ny = y + dy[i]
            let nt = min(t + 1, 8)
            let nArr = down(tempArr)
            if nx < 0 || nx >= 8 || ny < 0 || ny >= 8 || visited[nt][nx][ny] {continue}
            if tempArr[nx][ny] == "#" {continue}
            if nArr[nx][ny] == "#" {continue}

            queue.append((nt, nx, ny, nArr))
            visited[nt][nx][ny] = true
        }
    }

}

 

 

후기

개인적으로 이해하기 어려웠던 이유가 3차원 배열이 너무 이질적이었다.

코드

var arr = [[String]]()
for _ in 0..<8{
    arr.append(readLine()!.map{String($0)})
}
let dx = [1, -1, 0, 0, -1, -1, 1, 1, 0]
let dy = [0, 0, -1, 1, -1, 1, 1, -1, 0]

func down(_ arr: [[String]]) -> [[String]]{
    var temp = Array(arr.reversed()).dropFirst()
    temp.append([".",".",".",".",".",".",".","."])
    return Array(temp.reversed())
}
var result = false
func bfs(){
    var queue = [(Int, Int, Int, [[String]])]()
    var visited = Array(repeating: Array(repeating: Array(repeating: false, count: 8), count: 8), count: 9)
    let copiedArr = arr
    queue.append((0, 7, 0, copiedArr))
    visited[0][7][0] = true

    var idx = 0
    while queue.count > idx {
        let (t, x, y, tempArr) = queue[idx]
        idx += 1

        if x == 0 && y == 7{
            result = true
        }

        for i in 0..<9{
            let nx = x + dx[i]
            let ny = y + dy[i]
            let nt = min(t + 1, 8)
            let nArr = down(tempArr)
            if nx < 0 || nx >= 8 || ny < 0 || ny >= 8 || visited[nt][nx][ny] {continue}
            if tempArr[nx][ny] == "#" {continue}
            if nArr[nx][ny] == "#" {continue}

            queue.append((nt, nx, ny, nArr))
            visited[nt][nx][ny] = true
        }
    }

}
bfs()
if result{
    print(1)
}else{
    print(0)
}