알고리즘) 백준 7562번 나이트의 이동 Swift

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

---

예제

입력	출력
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1	5 28 0

 

---

문제 접근

예제를 살펴봅시다. 길이가 8이고 (0, 0)에서 (7, 0)으로 가는 방법은 이렇습니다.
하지만 다르게 가는 방법도 물론 존재합니다.

(0, 0) -> (2, 1) -> (4, 2) -> (6, 1) -> (8, 2) -> (7, 0)

다시 문제로 돌아와서, 나이트가 이동할 수 있는 지점은 기준점으로부터 1과 2로 교차된 지점입니다.

최소 이동 거리를 구하기 위해 2차원 배열인 visited에 몇 번 만에 방문하는 지 횟수를 기록합니다.
한 지점에 여러 번 방문 시 이동횟수가 계속 증가하는 현상을 맞닥뜨립니다.
그래서 방문 여부를 체크하기 위해 visited 요소 값을 모두 -1로 초기화합니다.
방문한 적 없는 지점에 대해서만 방문 횟수를 채워 넣습니다.
queue에 다음에 방문할 지점을 담아 하나씩 꺼내 더이상 방문할 지점이 없으면 반복문을 빠져 나옵니다.

풀이

풀이 속 출력 테스트 주석을 해제하여 실행해보면 이해가 빠르게 됩니다. 😊