[BOJ/Swift] 나이트의 이동 7562

Baekjoon Online Judge

단계별로 풀어보기 / DFS와 BFS / 나이트의 이동 7562

문제에 모든 정보 및 저작권 https://www.acmicpc.net/

---

Todo:

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

Constraints:

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

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

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

Input-Output

(출처 : https://www.acmicpc.net/problem/7562)

Solution.swift

let directions = [(2, -1), (1, -2), (1, 2), (2, 1), (-2, 1), (-1, 2), (-2, -1), (-1, -2) ]
let caseCount = Int(readLine()!)!

// (x, y) / arr[y][x]
func bfs(start: (Int, Int), end: (Int, Int), size: Int, _ directions: [(Int, Int)]) -> Int {
    guard start != end else { return 0 }

    var check = [[Bool]](repeating: [Bool](repeating: false, count: size), count: size)
    var visitQueue = [(start, 0)]
    check[start.1][start.0] = true

    while !visitQueue.isEmpty {
        let now = visitQueue.removeFirst()
        if now.0 == end { return now.1 }

        directions.forEach { direction in
            let next = (now.0.0 + direction.0, now.0.1 + direction.1)

            if next.0 >= 0, next.0 < size,
               next.1 >= 0, next.1 < size,
               !check[next.1][next.0] {
                check[next.1][next.0] = true
                visitQueue.append((next, now.1 + 1))
            }
        }
    }
    return 0
}


for _ in 0..<caseCount {
    let size = Int(readLine()!)!
    let start = readLine()!.split(separator: " ").map({ Int(String($0))! })
    let end = readLine()!.split(separator: " ").map({ Int(String($0))! })
    print(bfs(start: (start[0], start[1]), end: (end[0], end[1]), size: size, directions))
}

github Code Repository

How I tried this:

BFS의 기본을 지키면 잘 풀 수 있는 문제
현재 점에서 이동가능한 점들을 다음 방문할 점들로 큐에 담고
큐에 쌓인 점들을 모두 방문하다가 목적지에 도착하면 반복문을 마친다.

What I got is:

몇번 이동했는지 count를 세는걸 어떻게 할지 좀 더 고민해보아야겠다.

I have to study:

• inout 키워드
• BFS의 이해

문제에 관한 모든 저작권 : https://www.acmicpc.net/