[백준 06798] Knight Hop [Java]

문제

Below is an 8 × 8 chessboard on which we will designate square locations using the ordered pairs as indicated. For example, notice that piece A is at position (2, 2) and piece B is at position (4, 3).

A knight is a special game piece that can leap over other pieces, moving in the “L” pattern. Specifically, in the diagram below, K represents the knight’s starting position and the numbers 1 through 8 represent possible places the knight may move to.

Your program will read the starting location of the knight and output the smallest number of jumps or moves needed to arrive at a location specified in the second input.

입력

Your program will read four integers, where each integer is in the range 1...8. The first two integers represent the starting position of the knight. The second two integers represent the final position of the knight.

출력

Your program should output the minimum (non-negative integer) number of moves required to move the knight from the starting position to the final position. Note that the knight is not allowed to move off the board during the sequence of moves.

---

풀이

주어진 출발지와 도착지가 주어졌을 때 나이트를 이동해서 최소 몇번만에 도착지에 도달하는지 계산하는 문제다.

출발지와 도착지를 배열 형태로 입력받아주자.

 

그 다음 BFS를 통해 최소 움직임 횟수를 구해야 하는데 그 전에 체스판을 벗어나지 않았는지,

두 위치가 같은지 검사해줄 메서드를 선언하자.

나이트는 아래와 같이 움직일 수 있다.

bfs를 시작하기에 앞서 입력받은 위치가 처음부터 같은 경우 0을 반환하고 종료하고, 아니라면 탐색을 위한 초기화를 하자.

처음 위치부터 시작해서 반복문을 돌며 나이트가 이동할 수 있는 다음 위치를 구하자.

다음 위치가 범위를 벗어나지 않고, 방문한 적 없다면 

도착지와 같은지 비교후 다르다면 방문 표시와 함께 다음 탐색 대상으로 queue에 넣어주자.

---

소스코드

보기

---

출처

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