Swift) 백준 1600번 말이 되고픈 원숭이 - G3

https://www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

문제 풀이: bfs로 풀면 쉽게 풀릴듯 보이나, 한가지 고려해야할 점이 있다. 

O	X	O	O	X	O
O	O	O	O	X	O

단 한번만 점프가 가능하다고 가정하고, 다음과 같이 지도가 존재한다고 할때, (0,0)에 위치한 원숭이가 x축으로 점프를 한다고 가정해보자.

그러면 원중이의 위치는 (1,3)으로 위치하게 되고, (1,3)은 방문처리 하면, 목적지로 점프할 수 없으니 해당 점프는 더이상 나아갈 수 없다.

그 후 점프를 한번도 사용하지 않고 이동한다고 했을때, (1,3)으로 가려고 했지만, 방문 처리했으므로, 해당 위치로 가지 않는다.

 

이런 문제때문에 하나의 배열만 이용해서 방문처리를 하면 갈 수 없는 경우가 생기므로, 나는 남아있는 점프의 개수로 3차원 배열을 만들어서 각 점프 횟수에 관해 배열을 관리하여 문제를 해결했다.

 

참고로 swift로 removeFirst()를 할 시 O(n)의 시간이 걸리기에 시간 초과가 뜨므로, index값을 가리키는 변수를 두어 O(1)의 시간이 되도록 이를 변경했다.

import Foundation

let k = Int(readLine()!)!
let wh = readLine()!.split(separator: " ").map{ Int($0)! }
var map: [[Bool]] = []
var visited: [[[Bool]]] = Array(repeating: Array(repeating: Array(repeating: false, count: wh[0]), count: wh[1]), count: 31)
for _ in 0..<wh[1] {
    let input = readLine()!.split(separator: " ").map{ Int($0)==0 }
    map.append(input)
}

let mx = [0,1,0,-1]
let my = [-1,0,1,0]

let hx = [1,2,2,1,-1,-2,-2,-1]
let hy = [-2,-1,1,2,-2,-1,1,2]

struct Monkey {
    let count: Int
    let canJumpCount: Int
    let x: Int
    let y: Int
}

func validateCoordi(x: Int, y: Int, jumpCount: Int) -> Bool {
    if x < 0 || x >= wh[0] || y < 0 || y >= wh[1] {
        return false
    }
    return !visited[jumpCount][y][x] && map[y][x]
}

func solution() {
    var queue: [Monkey] = [.init(count: 0, canJumpCount: k, x: 0, y: 0)]
    var idx = 0
    while queue.count > idx {
        let popM = queue[idx]
        idx += 1
        if popM.x == wh[0]-1 && popM.y == wh[1]-1 {
            print(popM.count)
            return
        }
        for i in 0..<mx.count {
            let nextX = popM.x+mx[i]
            let nextY = popM.y+my[i]
            if validateCoordi(x: nextX, y: nextY, jumpCount: popM.canJumpCount) {
                queue.append(.init(count: popM.count+1, canJumpCount: popM.canJumpCount, x: nextX, y: nextY))
                visited[popM.canJumpCount][nextY][nextX] = true
            }
        }
        if popM.canJumpCount > 0 {
            for i in 0..<hx.count {
                let nextX = popM.x+hx[i]
                let nextY = popM.y+hy[i]
                if validateCoordi(x: nextX, y: nextY, jumpCount: popM.canJumpCount-1) {
                    queue.append(.init(count: popM.count+1, canJumpCount: popM.canJumpCount-1, x: nextX, y: nextY))
                    visited[popM.canJumpCount-1][nextY][nextX] = true
                }
            }
        }
        
    }
    print("-1")
}

solution()