[알고리즘] Swift -백준 #7562(나이트의 이동) -BFS

문제링크

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

7562번: 나이트의 이동

 

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

 

---

분석

나이트가 한 번에 이동할 수 있는 칸은 상하좌우 두 칸씩 이동 후 좌우로 한 칸씩으로 이동할 수 있다.

나이트가 몇 번 움직이면 원하는 칸으로 이동할 수 있는 지

 

풀이 과정

t = 테스트 케이스

• 첫째줄 = 체스판의 한 변의 길이 (정사각형)
• 둘째 줄 = 출발지
• 셋째 줄 = 목적지

출발지와 목적지가 주어질 때 목적지까지 갈 수 있는 최소 거리를 구하는 문제
최소 거리를 구하는 문제는 BFS 사용

 

풀이

class Queue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        self.enQueue = queue
    }
    
    func push(_ element: T) {
        enQueue.append(element)
    }
    
    func pop() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }

    func front() -> T? {
        let newQue = deQueue.reversed() + enQueue
        return newQue.first
    }
}

let t = Int(readLine()!)!

for _ in 0..<t {
    let l = Int(readLine()!)!
    let start = readLine()!.split(separator: " ").map{ Int($0)!}
    let end = readLine()!.split(separator: " ").map{ Int($0)!}
    
    var checkArr = [[Bool]](repeating: Array(repeating: false, count: l), count: l)
    var count = [[Int]](repeating: Array(repeating: 0, count: l), count: l)
    
    let dx = [-2, -2, -1, -1, 1, 1, 2, 2]
    let dy = [-1, 1, -2, 2, -2, 2, -1, 1]
    
    func isValid(y: Int, x: Int) -> Bool {
        return 0 <= y && y < l && 0 <= x && x < l ? true : false
    }

    func bfs() {
        checkArr[start[1]][start[0]] = true

        let q = Queue<[Int]>([])
        q.push([start[1], start[0]])
        
        while !q.isEmpty {
            let pop = q.pop()
            let y = pop[0]
            let x = pop[1]

            if y == end[1] && x == end[0] {
                break
            }
            
            for k in 0..<8 {
                let nextY = y + dy[k]
                let nextX = x + dx[k]
                
                if isValid(y: nextY, x: nextX) && !checkArr[nextY][nextX] {
                    count[nextY][nextX] = count[y][x] + 1
                    checkArr[nextY][nextX] = true
                    q.push([nextY, nextX])
                }
            }
        }
    }
    bfs()
    print(count[end[1]][end[0]])
}

 

결과

 

 

 

 

---

📂  정리

상하좌우가 아닌 이동할 수 있는 위치를 지정해주는 dx, dy만 설정해주면

나머지는 똑같은 길찾기 문제이다.