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 와 같이 표현할 수 있다.

소스코드

후기

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