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

문제 소개

벽이 움직이는 미로를 탈출하는 문제이다.

문제 풀이

벽이 아래로 움직이기 때문에 i 와 j 를 바꿔서 배열에 넣어주고 round 마다 +1 을 해주어 갈 수 있는지 없는지를 판별했다.

import Foundation

let moves = [(1, -1), (1, 0), (0, -1), (0, 0), (-1, 0), (0, 1), (-1, -1), (-1, 1), (1, 1)]
var walls = Array(repeating: [Int](), count: 8)

for i in 0..<8 {
    let input = Array(readLine()!).map { String($0) }
    
    for j in 0..<8 {
        if input[j] == "#" {
            walls[j].append(i)
        }
    }
}

func check(_ i: Int, _ j: Int, _ round: Int) -> Bool {
    for wall in walls[j] {
        if i == wall + round { return false }
        if i == wall + round + 1 { return false }
    }
    
    return true
}

var queue = [(7, 0, 0)]
var idx = 0
var visit = Array(repeating: Array(repeating: Array(repeating: false, count: 8), count: 8), count: 1)
let newVisit = Array(repeating: Array(repeating: false, count: 8), count: 8)

while queue.count > idx {
    let popped = queue[idx]
    idx += 1
    
    if popped.0 == 0 && popped.1 == 7 {
        print(1)
        exit(0)
    }
    
    if visit.count == popped.2 {
        visit.append(newVisit)
    }
    
    for move in moves {
        let i = popped.0 + move.0
        let j = popped.1 + move.1
        let r = popped.2
        
        if 0..<8 ~= i && 0..<8 ~= j {
            if check(i, j, r) && !visit[r][i][j] {
                visit[r][i][j] = true
                queue.append((i, j, r + 1))
            }
        }
    }
}

print(0)

 
결과는 아주 빠르게 나왔다.