[BOJ] 백준 7562번 : 나이트의 이동 (JAVA)

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

 

   

 

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

 

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

 

출력

각 테스트 케이스마다 나이트가 몇 번만에 이동할 수 있는지 출력한다.

 

 

풀이

전형적인 BFS 문제였습니다.

 

보통, BFS를 이용하여 상하좌우를 이동하는 문제가 많았는데, 이번에는 이동하는 구간이 8개였습니다.

대략 (4, 4)를 기준으로 잡고, 8개의 구간에 따라 점이 어떻게 바뀌는지 관찰하면, 쉽게 rangeX 배열과 rangeY 배열을 구할 수 있습니다. 

이후에는 기본적인 BFS 코드를 작성하여 시작점에서 끝점에 도달하는 순간을 포착하면 됩니다.

 

아래 소스코드를 통해 확인해 보시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.