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

안녕하세요 코코종입니다!

오늘은 BFS문제인 나이트의 이동을 풀어보겠습니다.

 

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

7562번: 나이트의 이동

//
//  main.swift
//  Algorithm
//
//  Created by kokojong on 2022/03/29.
//


// 7562 나이트의 이동
import Foundation

let n = Int(readLine()!)!

for _ in (0..<n) {
    
    let l = Int(readLine()!)!
    
    var board = Array(repeating: Array(repeating: 0, count: l), count: l) // l * l
    
    let now = readLine()!.components(separatedBy: " ").map({Int($0)!})
    let c1 = now[0]
    let r1 = now[1]
    
    let to = readLine()!.components(separatedBy: " ").map({Int($0)!})
    let c2 = to[0]
    let r2 = to[1]
    
    var queue : [[Int]] = []
    
    let dc = [1, 2, 2, 1, -1, -2, -2, -1] // x좌표 c
    let dr = [-2, -1, 1, 2, 2, 1, -1, -2] // y좌표 r
    
    queue.append([c1, r1])
    board[c1][r1] = 0
    
    var index = 0
    
    while queue.count > index {
        let q = queue[index]
        
        let c = q[0]
        let r = q[1]
        
        index += 1
        
        if r == r2 && c == c2 {
//            print("도착",board[c][r],c,r)
            print(board[c][r])
            break
        }
        
        for i in 0..<8 {
            let cc = c + dc[i]
            let rr = r + dr[i]
            
            if cc <= l-1 && cc >= 0 && rr >= 0 && rr <= l-1 {
                
                if board[cc][rr] == 0 {
                    board[cc][rr] = board[c][r] + 1
                    queue.append([cc,rr])
                }
                
            }
        }
    }
    
    
}

 

---

 

이 문제는BFS의 대표적인 문제를 살짝 변형했다고 보이네요!

원래는 미궁처럼 상하좌우만 이동했다면 이번에는 8가지 움직임이 있습니다.

기본적인 아이디어는 같고 저같은 경우에는 index오류가 발생해서 rr과 cc를 먼저 체크하고 그 안에서 board[cc][rr]에 대한 체크를 했습니다. x y로 처음에 하다가 헷갈려서 r c로 좌표의 이름을 바꿨더니 훨씬 덜 헷갈리게 되었습니다!

 

어제 풀었던 '벽 부수고 이동하기' 보다 훨씬 쉬워서 금~방 풀었네요 ㅎㅎ 그럼 20000~~