99클럽 코테 스터디 9일차 TIL: BFS

문제

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

풀이

나이트가 해당 좌표로 최소 몇 번 만에 이동할 수 있는지 구하는 문제
최소 몇번 -> 최단 거리를 뜻하기 때문에 BFS를 떠올려서 풀이할 수 있었다.
일단 나이트의 이동은 8방향이다.
나이트의 현재 위치에서 이동할 수 있는 방향을 확인하기 위해 dy, dx 값을 배열로 만들었다.

let dy = [2, 1, -1, -2, -2, -1, 1, 2]
let dx = [1, 2, 2, 1, -1, -2, -2, -1]

와 같은 형식으로 만들었다.

let position = [(2, 1), (1, 2), (-1, 2)...(2, -1)]

과 같이 만들어도 무방하지만 나는 첫번째 방법을 선호한다.

또한 나이트의 현재 위치에서 이동하려는 위치가 체스판을 넘어가면 안된다.
체스판의 크기는 가로, 세로 0 ~ l 의 range에 포함되어야 한다.

Swift에서는 x >= 0 && x < l을 0..<l ~= x 와 같이 표현할 수 있다.

소스코드

	let dy = [2, 1, -1, -2, -2, -1, 1, 2]
	let dx = [1, 2, 2, 1, -1, -2, -2, -1]
	let t = Int(readLine()!)!
	for _ in 0..<t { solution() }
	func solution() {
	let l = Int(readLine()!)!
	var board = [[Bool]](repeating: [Bool](repeating: false, count: l), count: l)
	let start = readLine()!.split { $0 == " " }.map { Int($0)! }
	let startX = start[0], startY = start[1]
	let end = readLine()!.split { $0 == " " }.map { Int($0)! }
	let endX = end[0], endY = end[1]
	func isValidCoord(y: Int, x: Int) -> Bool {
	return 0..<l ~= y && 0..<l ~= x
	}
	func bfs(y: Int, x: Int) {
	var queue = [(y, x, 0)]
	var index = 0
	board[y][x] = true
	while queue.count > index {
	let y = queue[index].0
	let x = queue[index].1
	let c = queue[index].2
	board[y][x] = true
	if y == endY && x == endX {
	print(c)
	break
	}
	for i in 0..<8 {
	let ny = y + dy[i]
	let nx = x + dx[i]
	if isValidCoord(y: ny, x: nx) && !board[ny][nx] {
	board[ny][nx] = true
	queue.append((ny, nx, c + 1))
	}
	}
	index += 1
	}
	}
	bfs(y: startY, x: startX)
	}

view raw 7562_나이트의 이동.swift hosted with ❤ by GitHub

후기

어렵지 않게 풀 수 있던 문제였다.
이 문제를보니 예전에 풀었던 백트래킹 문제인 N-Queen 문제가 떠올랐다..