문제 링크 (opens new window)

문제 요약

1. 원숭이가 0,0에서 W-1, H-1 도착지점까지 움직이는데 소요된 전체 턴 수를 출력해야 한다.
2. 원숭이는 체스 나이트처럼 움직일 수 있는데, K번 이상으로는 움직이지 못한다.
3. K번 이상 말처럼 움직인 뒤로부터는 상하좌우 인접한 곳으로만 이동 가능하다.

접근방식

1. 도착 지점까지의 최단거리를 구해야 하므로 BFS를 활용한다.
2. 원숭이가 말처럼 움직이는 횟수에 제한이 있으므로, 말처럼 움직이는 무빙과 인접한 상하좌우 무빙을 마음대로 섞어서 움직여서는 안된다.
3. visited배열을 딕셔너리로 생성한다. 딕셔너리의 키값이 말처럼 움직인 횟수값이 되고, 밸류는 visited 2차원 배열이 된다.
4. 큐 엘리먼트 타입은 (Int, Int, Int)로 선언하여 (y, x, 말처럼 움직인 횟수)로 처리한다.
5. 원숭이 무빙으로 움직이면 큐에 (nextY, nextX, 현재 말처럼 움직인 횟수)를 큐잉한다.
6. 말처럼 움직이면 큐에 (nextY, nextX, 현재 말처럼 움직인 횟수 + 1)을 큐잉한다.
7. 원숭이처럼 움직일때 현재 말처럼 움직인 횟수에서 이미 방문한 위치라면 continue한다.
8. 말처럼 움직일때 현재 말처럼 움직인 횟수 + 1에서 이미 방문한 위치라면 continue한다.
9. 나머지는 일반 BFS 풀이와 동일하다.

풀이

import Foundation

struct Queue<T> {
    var array: [T?] = []
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil }

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

let K = Int(readLine()!)!
let WH = readLine()!.split(separator: " ").map { Int($0)! }; let W = WH[0]; let H = WH[1]
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: W), count: H)
var visited: [Int: [[Int]]] = [:]
let dy = [-1, 0, 1, 0]; let dx = [0, -1, 0, 1]
let dyHorse = [2, 2, 1, -1, -2, -2, 1, -1]; let dxHorse = [-1, 1, -2, -2, -1, 1, 2, 2]
var result = Int.max

for i in 0..<H {
    adj[i] = readLine()!.split(separator: " ").map { Int($0)! }
}

var q = Queue<(Int, Int, Int)>()
q.enqueue((0, 0, 0))

while !q.isEmpty {
    guard let here = q.dequeue() else { break }

    if visited[here.2] == nil {
        visited[here.2] = .init(repeating: .init(repeating: 0, count: W), count: H)
    }

    for i in 0..<4 {
        let ny = dy[i] + here.0
        let nx = dx[i] + here.1

        if ny < 0 || nx < 0 || ny >= H || nx >= W || adj[ny][nx] == 1 { continue }

        if visited[here.2]![ny][nx] != 0 {
            continue
        } else {
            visited[here.2]![ny][nx] = visited[here.2]![here.0][here.1] + 1
            q.enqueue((ny, nx, here.2))
        }
    }

    if here.2 == K { continue }

    if visited[here.2 + 1] == nil {
        visited[here.2 + 1] = .init(repeating: .init(repeating: 0, count: W), count: H)
    }

    for i in 0..<8 {
        let ny = dyHorse[i] + here.0
        let nx = dxHorse[i] + here.1

        if ny < 0 || nx < 0 || ny >= H || nx >= W || adj[ny][nx] == 1 { continue }

        if visited[here.2 + 1]![ny][nx] != 0 {
            continue
        } else {
            visited[here.2 + 1]![ny][nx] = visited[here.2]![here.0][here.1] + 1
            q.enqueue((ny, nx, here.2 + 1))
        }
    }
}

for (_, value) in visited {
    if W == 1 && H == 1 && adj[0][0] == 0 {
        print(0)
        exit(0)
    }

    if value[H-1][W-1] != 0 {
        result = min(value[H-1][W-1], result)
    }
}

if result == 0 {
    print(-1)
} else if result == Int.max {
    print(-1)
} else {
    print(result)
}