Legacy/Be Refactoring..
[BOJ/Swift] 나이트의 이동 7562
Marco
2021. 9. 10. 01:07
728x90
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/
728x90