[Swift Algorithm] 나이트의 이동 BOJ #7562

문제 설명

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

 

입력

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

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

 

출력

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

 

입출력 예제

입력

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

출력

5
28
0

 

내 문제 풀이

let cases = Int(readLine()!)!
var dx = [-2, -1, 1, 2, 2, 1, -1, -2], dy = [1, 2, 2, 1, -1, -2, -2, -1] // 나이트의 이동을 위한 좌표값 변화량
var result = [Int]()

// 입력된 테스트 케이스의 수 만큼 반복
for _ in 0..<cases {
    let n = Int(readLine()!)! // 체스 보드 한 변의 길이
    let start = readLine()!.split(separator: " ").map({Int(String($0))!}) // 시작점
    let target = readLine()!.split(separator: " ").map({Int(String($0))!}) // 목적지
    
    if (start[0], start[1]) == (target[0], target[1]) { result.append(0) } // 처음부터 시작점과 목적지가 같을 경우 바로 result에 0추가
    else {
        let target_check = (target[0], target[1]) // 목적지를 튜플로 생성
        var queue = [(start[0], start[1])] // 큐 생성, 시작점을 튜플로 만들어서 넣어주기
        var board = Array(repeating: Array(repeating: 0, count: n), count: n) // 경로마다 걸린 시간을 누적해주면서 체크하기 위한 보드 배열
        var arrive = 0 // 목적지에 도착했는지 안했는지 체크하기 위함 (0이면 도착x)
        
        var index = 0
        while !queue.isEmpty {
            let (x, y) = queue[index]
            index += 1
            
            for i in 0..<8 {
                let dx = x + dx[i]
                let dy = y + dy[i]
               
                if dx < 0 || dy < 0 || dx >= n || dy >= n || board[dx][dy] != 0 { continue } // 예외

                board[dx][dy] = board[x][y] + 1 // 해당 자리까지 걸린 시간 누적
                
                if target_check == (dx, dy) { arrive = board[dx][dy]; break } // 탐색한 자리가 목적지와 같을 경우
                queue.append((dx, dy)) // 아닐 경우 큐에 추가
            }
            
            if arrive != 0 { result.append(arrive); break } // arrive가 0이 아닐 경우 (목적지에 도착)
        }
    }
}

print(result.map({String($0)}).joined(separator: "\n"))

👉 bfs 문제로, 나이트가 이동할 수 있는 모든 경우의 수를 고려해주는게 포인트!

• 지금까지 풀었던 bfs 문제들과 이 문제의 가장 큰 차이점은,
  나이트는 상하좌우 탐색이아니라 총 8가지의 경로를 탐색해줘야한다는 것이다.
  따라서 그에 맞는 좌표 변화량을 넣어서 dx, dy 배열을 생성해주었다.
• 우선 if로 처음부터 시작점과 목적지가 같을 경우를 예외로 빼주었다.
  그리고 그 외의 경우에는 bfs 탐색을 시작했다.
• while문으로 bfs 탐색을 해주었고, index 변수를 이용해서 큐를 다뤘다.
  나이트가 이동할 수 있는 경로는 총 8개이므로 while문 안의 for문으로 8번 반복해주었다.
• for문에서는 dx, dy 배열을 이용하여 다음 탐색 위치를 결정하고, 그 위치가 적절한지 판단했다.
  그 위치가 보드 바깥이거나 해당 위치에 0이 아닌 값이 저장되어있다면 해당 반복은 종료했다.
  (모든 경로 탐색 시 해당 자리까지의 탐색 누적 시간을 저장했으므로, 0이 아닌 값이 저장되어있다는 뜻은 해당 자리는 이미 탐색한적이 있다는 의미이다. 따라서 중복 탐색을 피하기 위함!)
  예외처리에서 걸리지 않았다면 보드 배열의 해당 위치에 누적된 시간을 저장해주었고,
  탐색한 자리가 목적지와 같을 경우에는 arrive 변수에 누적된 시간을 넣고 for문을 종료한다.
  아직 목적지에 도달하지 못했을 경우에는 큐에 다음 탐색지를 추가하고 실행을 계속한다.
• 위에서 arrive 변수에 누적된 시간이 저장되었을 경우에는 arrive가 0이 아니게되므로
  목적지에 도착한것으로 판단하고, result 배열에 값을 추가하고 while문을 종료한다.

 

💡 피드백

• 상하좌우가 아닌 총 8개 경로 탐색을 위한 dx, dy 배열을 생성해주려고 한 부분에서 조금 시간이 지체되었고, 나머지는 이전에 풀었던 문제들과 비슷해서 금방 풀어낼 수 있었다.

 

---

문제

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