[DFS & BFS] 백준 : 7562_나이트의 이동

[inseonyun]

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

[inseonyun]

문제 요구사항

• 입력 첫줄에는 Test_case가 주어진다.
• 각 Test_case의 첫줄에는 체스판의 크기가 주어진다.( 4 ≤ l ≤ 300 )
• 각 Test_case의 둘째줄에는 나이트의 현위치, 둘째줄에는 도착지가 있다.
• 이때, 각 Test_case마다 현위치에서 도착지까지 몇 번만에 이동할 수 있는지 출력하라.

접근 방법

• 나이트의 이동 방법에 따른 가중치 좌표 nightx와 nighty 배열을 생성해준다.
• 다른 BFS 문제들과 마찬가지로 최소 몇 번만에 갈 수 있는지를 구하는 문제이기 때문에 체스 맵 배열을 선언 해줘서 해당 체스 맵에 계속 이동 횟수를 더해 나간다. (이 문제에서는 체스맵 데이터를 입력받지 않기 때문에 카운트 해나갈 체스맵 2차원 배열 하나면 됨)

풀이 순서

1. Test_case의 개수를 입력 받는다.
2. 각 Test_case에 해당하는 데이터(맵크기, 시작점, 도착점)을 입력받는다.
3. BFS 수행
   • q에 시작점 x, y 좌표를 넣어준다.
   • q가 비어있을 때까지 반복문을 돌면서 도착점과 같으면 종료한다.
   • for문을 돌면서 나이트를 이동시키도록 한다.
   • 위 작업 반복 수행
4. 최소 이동거리를 계속 더해나간 배열의 도착점 x, y칸에 최소 이동거리가 담겨져 있으므로, 해당 값을 return 한다.
5. 이 과정을 각 Test_case마다 반복하여 결과를 구한다.

[inseonyun]

[문제 풀이 결과]