[백준] 7562번 나이트의 이동 [Swift]

문제 링크

문제

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

입력

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

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

출력

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

문제 풀이

이 문제는 아주 기본적인 DFS, BFS 문제 였습니다.

하지만 기본적인 문제들은 이동 할 수 있는 가짓 수가 상하좌우로 4가지 였다면 이 문제는 총 8가지의 경우의 수가 존재합니다.

DFS, BFS 아무거나로 풀 수 있지만 저는 BFS를 사용해서 풀었습니다!

따라서 큐를 사용했으며 큐에 넣는 데이터는 세 개의 값을 가지는 정수형 배열로 넣어줬는데, 이는 위치와 지금까지 몇 번 움직였는지를 기억하기 위해서 그렇게 만들어줬습니다.

그리고 DFS, BFS에서 꼭 만들어줘야하는 방문했는지에 대한 여부를 저장하는 배열도 만들어줬습니다.

 

저는 큐에 몇 번 움직였는지를 저장했는데, 방문여부를 체크하는 테이블에 저장하는 방법도 있을것 같아요.

어쨌든 모두 준비한 뒤에 간단하게 BFS로 모두 비교하면서 답을 구하면 됩니다.

소스 코드

import Foundation

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

func solution() {
    let n = Int(String(readLine()!))!
    
    // 나이트가 이동할 수 있는 모든 경우의 수
    let dx = [-1, -2, -1, -2, 1, 2, 2, 1]
    let dy = [-2, -1, 2, 1, -2, -1, 1, 2]
    
    for _ in 0..<n {
        let size = Int(String(readLine()!))!
        let start = readLine()!.split(separator: " ").map({Int(String($0))!})
        let end = readLine()!.split(separator: " ").map({Int(String($0))!})
        
        let queue = Queue([[Int]]())
        // 시작점과 몇 번 움직인 것인지를 나타낼 값을 같이 queue에 넣습니다.
        queue.push(start + [0])
        // 방문 여부를 표시할 배열
        var visited: [[Bool]] = [[Bool]](repeating: [Bool](repeating: false, count: size), count: size)
        // 시작 점은 방문했다고 표시합니다
        visited[start[0]][start[1]] = true
        
        if start == end {
            print(0)
            continue
        }
        
        while(!queue.isEmpty) {
            let now = queue.pop()!
            let position = [now[0], now[1]]
            let times = now[2]
            // 만약 현재 위치와 도착 위치가 같다면 현재 이동횟수를 출력하고 반복을 종료합니다.
            if position == end {
                print(times)
                break
            }
            for i in 0..<8 {
                let newX = position[1] + dx[i]
                let newY = position[0] + dy[i]
                
                if newX >= size || newY >= size || newX < 0 || newY < 0 {
                    continue
                } else if !visited[newY][newX]{
                    queue.push([newY, newX, times+1])
                    visited[newY][newX] = true
                }
            }
        }
    }
    
}

solution()