[Swift] 백준_말이 되고픈 원숭이(1600)

문제

 

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

1600번: 말이 되고픈 원숭이

 

 

풀이

 

인덱스 실수를 알아채지 못해서 몇시간이나 걸림...

 

이 문제는 벽 부수고 이동하기 문제와 비슷하게 해결했다. 중요한 포인트는 3차원 배열이었다. x,y 값뿐만아니라 점프한 횟수도 갖고 있어야한다. 

 

이 포인트만 이용한다면 어렵지 않게 해결할 수 있다. 상하좌우로 가는 경우와 점프하는 경우 모두 큐에 담아주면 된다. 이때, 주의해야 할 점은 -1(아직 지나지 않은 칸)일때만 값을 추가하면 안된다는 것이다.

큐에는 점프해서 간 경우와 인접한 곳으로 이동한 경우가 동시에 들어있기때문에 반드시 시간순서라는 보장이 없다. 더 빠르게 갈 수 있는데 큐에 늦게 들어가는 경우가 있다는 얘기이다. 

그렇기 때문에 갈 곳의 check값이 -1인 경우만 확인하면 안되고 -1이 아닌 경우에도 이전 값에 +1 한 값과 비교해서 더 작은 값으로 수정해주면된다.

import Foundation

let k = Int(readLine()!)!
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
var board: [[Int]] = []
for _ in 0..<input[1] {
    board.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
var check = Array(repeating: Array(repeating: Array(repeating: -1, count: k + 1), count: input[0]), count: input[1])
var queue = [[0,0,0]] // x, y, 횟수
var idx = 0
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
let jumpX = [1,2,2,1,-1,-2,-2,-1]
let jumpY = [2,1,-1,-2,-2,-1,1,2]
check[0][0][0] = 0
outer: while idx < queue.count {
    let current = queue[idx]
    if current[0] == input[1] - 1 && current[1] == input[0] - 1 {
        print(check[current[0]][current[1]][current[2]])
        exit(0)
    }
    idx += 1
    for i in 0..<dx.count {
        let newX = current[0] + dx[i]
        let newY = current[1] + dy[i]
        if newX < 0 || newY < 0 || newX >= input[1] || newY >= input[0] {
            continue
        }
        if board[newX][newY] == 1 {
            continue
        }
        if check[newX][newY][current[2]] != -1 {
            if check[newX][newY][current[2]] > check[current[0]][current[1]][current[2]] + 1 {
                check[newX][newY][current[2]] = check[current[0]][current[1]][current[2]] + 1
                queue.append([newX,newY,current[2]])
            }
        } else {
            check[newX][newY][current[2]] = check[current[0]][current[1]][current[2]] + 1
            queue.append([newX,newY,current[2]])
        }
    }
    for i in 0..<jumpX.count {
        let newX = current[0] + jumpX[i]
        let newY = current[1] + jumpY[i]
        let newJ = current[2] + 1
        if newJ > k {
            continue outer
        }
        if newX < 0 || newY < 0 || newX >= input[1] || newY >= input[0] {
            continue
        }
        if board[newX][newY] == 1 {
            continue
        }
        if check[newX][newY][newJ] != -1 {
            if check[newX][newY][newJ] > check[current[0]][current[1]][current[2]] + 1 {
                check[newX][newY][newJ] = check[current[0]][current[1]][current[2]] + 1
                queue.append([newX,newY,newJ])
            }
        } else {
            check[newX][newY][newJ] = check[current[0]][current[1]][current[2]] + 1
            queue.append([newX,newY,newJ])
        }
    }
}
print(-1)

 

 

_____________________________________________________________________________________________________

 

 

내 코드를 검토할 땐 왜 꼼꼼하게 못보는 것일까