7562번: 나이트의 이동

문제 풀이 아이디어

동서남북 대신 8방향을 탐색을 한다는 점을 제외하면 기존의 bfs로 최단경로 찾기와 동일한 원리입니다.

# 사용해야 하는 알고리즘 = bfs
  : 최단 거리로 가야하므로 bfs를 사용하면 됩니다.
  : 다만 기존의 동서남북 탐색 대신 나이트의 이동 방법 (8가지)를 구현해야합니다.

# 문제 풀이 아이디어
  : 나이트는 한 위치에서 총 8가지로 움직일 수 있습니다.
  : 각각의 이동을 dr, dc에 미리 구현해놓고 탐색하면 됩니다.

# 의사코드
  1. 입력을 받고 I**2의 방문체크용 인접배열을 선언합니다.
  2. 나이트의 이동 방법에 맞추어 r, c 좌표의 변경 쌍을 미리 선언합니다.
  3. 시작 좌표와 거리(0)을 queue에 넣고 bfs를 실시합니다.
      3-1. 8방향으로 탐색하면서 이동가능한 좌표라면 거리 + 1을 해서 push합니다.
      3-2. pop한 결과가 도착 좌표와 동일하면 거리를 출력합니다.

코드

// 나이트의 이동

// 말의 위치 구조체
struct Position {
    let r: Int
    let c: Int
    let d: Int
    
    init(_ r: Int, _ c: Int, _ d: Int) {
        self.r = r
        self.c = c
        self.d = d
    }
}

// 큐 구조체
struct Queue {
    var queue = [Position]()
    var index = 0
    
    var isEmpty: Bool {
        return queue.count - index == 0
    }
    
    mutating func push(_ p: Position) {
        queue.append(p)
    }
    
    mutating func pop() -> Position {
        defer {
            index += 1
        }
        return queue[index]
    }
}

// bfs 구현
func bfs() {
    // 좌표가 유효한지 구하는 함수 (I가 테스트 case 마다 달라지므로 bfs 안에 구현)
    func isValid(_ r: Int, _ c: Int) -> Bool {
        return r >= 0 && r < I && c >= 0 && c < I
    }
    
    // 입력 받기
    let I = Int(readLine()!)!
    var check = Array(repeating: Array(repeating: false, count: I), count: I)
    let startInput = readLine()!.split(separator: " ").map { Int(String($0))! }
    let endInput = readLine()!.split(separator: " ").map { Int(String($0))! }
    
    // queue에 출발점 push
    var queue = Queue()
    queue.push(Position(startInput[0], startInput[1], 0))
    check[startInput[0]][startInput[1]] = true
    
    // 완전 탐색 시작
    while !queue.isEmpty {
        // 목적지에 도착하면 거리 출력
        let now = queue.pop()
        if now.r == endInput[0] && now.c == endInput[1] {
            print(now.d)
            return
        }
        
        // 8방향 탐색
        for i in 0..<8 {
            let nr = now.r + dr[i]
            let nc = now.c + dc[i]
            if isValid(nr, nc) && !check[nr][nc] {
                queue.push(Position(nr, nc, now.d + 1))
                check[nr][nc] = true
            }
        }
    }
}

// 테스트 케이스 횟수 입력 받기
let T = Int(readLine()!)!

// 나이트의 8가지 이동에 대한 좌표 변화
let dr = [-1, -2, -2, -1, 1, 2, 2, 1]
let dc = [-2, -1, 1, 2, 2, 1, -1, -2]

for _ in 0..<T {
    bfs()
}