(백준 c++)7562 나이트의 이동

문제

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

입력

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

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

출력

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

 

BFS를 이용하여 문제 풀이.

우선 나이트가 이동할 수 있는 범위를 나타내는 배열 2개를 선언하였다.

나이트가 8개의 방향으로 이동할 수 있기 때문에 각 범위에 맞게 x, y에 더할 수 있는 값을 arr_x, arr_y 배열에 저장한다.

 

n개의 케이스 만큼 반복.

차례대로 보드의 크기, 현재 나이트의 좌표, 나이트가 이동하려는 좌표를 받아온다.

방문 여부를 알 수 있는 2차원 vector를 보드의 크기만큼 선언하여 false로 초기화 한다.

다음으로 큐와 answer, 탈출하기 위한 bool형 변수를 선언.

 

현재 나이트가 있는 위치를 큐에 넣어두고, 방문했다고 바꿔주도록 한다.

그 후 BFS로 큐가 비어있을 때까지 반복하면서, 조건에 맞게 나이트의 이동 위치를 큐에 넣어주면 된다.

큐의 맨 앞에 있는 요소를 꺼내 목표 위치와 같은지 확인하여 같지 않다면 이동 여부를 검사하여 큐에 push하도록 한다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, I, current_x, current_y, target_x, target_y;
	int arr_x[8] = {-2, -1, 1, 2, -2, -1, 1, 2};
	int arr_y[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> I;
		cin >> current_x >> current_y;
		cin >> target_x >> target_y;
		
		vector<vector<bool>> visited(I, vector<bool>(I, false));
		queue<pair<int, int>> q;
		int answer = 0;
		bool exit = false;
		
		q.push(make_pair(current_x, current_y));
		visited[current_x][current_y] = true;

		while(!q.empty()){
			int size = q.size();
			for(int j = 0; j < size; j++){
				int x = q.front().first;
				int y = q.front().second;
				q.pop();
				
				if(x == target_x && y == target_y){
					cout << answer << endl;
					exit = true;
					break;
				}
				else{
					for(int k = 0; k < 8; k++){
						if(x + arr_x[k] >= 0 && x + arr_x[k] < I && y + arr_y[k] >= 0 && y + arr_y[k] < I && !visited[x + arr_x[k]][y + arr_y[k]]){
							q.push(make_pair(x + arr_x[k], y + arr_y[k]));
							visited[x + arr_x[k]][y + arr_y[k]] = true;
						}
					}
				}
			}

			if(exit){
				break;
			}
			answer++;
		}
	}
	return 0;
}