[Swift] 백준_나이트의 이동(7562)

문제

 

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

7562번: 나이트의 이동

 

 

풀이

 

이 문제는 상하좌우가 아니라 8방향으로 갈 수 있기때문에 dx dy를 1,-1만 생각하지 않고 1,2,-1,-2를 생각해주면 된다.

 

BFS를 이용해서 풀었다.

 

시작점을 큐에 넣어준 뒤, 8방향에 대해 각각 조건을 만족한다면 이전 값에 1을 더해주어 chess[newX][newY]에 넣어주었다.

이때, newX와 newY가 target과 같다면 결과를 출력하고 반복문을 탈출하였다.

 

처음에는 queue를 이용할때 removeFirst()를 이용해 current에 넣어주었다. 근데 시간이 좀 오래 걸려서 인덱스를 이용해봤더니 시간을 절반이나 단축시킬 수 있었다.

 

한 번 시간을 줄인 뒤에도 다른 답들과 비교해봤을때 시간이 조금 더 걸리는 경향이 있어 더 줄일 수 있는지 확인해보았고, newX와 newY를 target과 비교해주는 부분을 가장 처음으로 두고 필요없는 계산을 줄였더니 다시 반으로 줄일 수 있었다.

import Foundation

let caseCount = Int(readLine()!)!
let dx = [1,2,2,1,-1,-2,-2,-1]
let dy = [2,1,-1,-2,-2,-1,1,2]
for _ in 0..<caseCount {
    let l = Int(readLine()!)!
    let start = readLine()!.split(separator: " ").map { Int(String($0))! }
    let target = readLine()!.split(separator: " ").map { Int(String($0))! }
    var queue:[[Int]] = []
    var chess = Array(repeating: Array(repeating: -1, count: l), count: l)
    chess[start[0]][start[1]] = 0
    var idx = 0
    queue.append(start)
    outer: while idx < queue.count {
        let current = queue[idx]
        if current == target {
            print(0)
            break
        }
        idx += 1
        for i in 0..<dx.count {
            let newX = current[0] + dx[i]
            let newY = current[1] + dy[i]
            if newX == target[0] && newY == target[1] {
                print(chess[current[0]][current[1]] + 1)
                break outer
            }
            if newX < 0 || newY < 0 || newX >= l || newY >= l {
                continue
            }
            if chess[newX][newY] != -1 {
                continue
            }
            chess[newX][newY] = chess[current[0]][current[1]] + 1
            queue.append([newX,newY])
        }
    }
}

 

_____________________________________________________________________________________________________

 

줄여서 뿌듯하긴한데 그래도 아직 1페이지에 있는 시간들보단 길어서 더 줄일 수 있는 부분이 있는지 확인해봐야 할 것 같다. 푸는 방식은 대부분 비슷한 것 같아 입출력쪽이나 비효율적인 부분이 있는지를 확인해봐야 할듯