백준 나이트의 이동 C++

 

 

입력

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

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

출력

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

예제 입력 1 복사

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

 

 

=> 간단한 BFS문제입니다. 

=> BFS로 탐색을 하며 target 좌표를 찾았을 경우 해당 값까지 이동한 거리를 출력하면 됩니다. 

=> BFS를 사용하기 때문에 queue를 사용해야하며 좌표를 표현하기 위해 pair형 자료구조를 활용하였습니다. 

=> 움직일 수 있는 위치를 계산하기 위해 dx[8] , dy[8] 배열을 이용하여 계산하였습니다. 

=> 자세한 풀이는 아래의 그림을 통해 확인할 수 있습니다. 

 

 

 

#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
#include <queue>
#include <utility>

using namespace std;

pair<int, int> cur, target;
int arr     [301][301];
int visited[301][301];
int dx[8] = { -2,-1,1,2,2,1,-1,-2 };
int dy[8] = { 1,2,2,1,-1,-2,-2,-1 };
queue<pair<int, int>> Q;
int M, D;

void reset()
{
	while (!Q.empty()) Q.pop();
	for (int i = 0; i < 301; i++)
	{
		for (int j = 0; j < 301; j++)
		{
			visited[i][j] = 0;
			arr[i][j] = 0;
		}
	}
}
void BFS(int x, int y)
{
	Q.push(make_pair(x,y));
	visited[x][y] = true; 
	while (!Q.empty())
	{
		int QX = Q.front().first;
		int QY = Q.front().second;

		Q.pop();

		if ((QX == target.first) && (QY == target.second))
		{
			cout << arr[QX][QY] << '\n';
			while (!Q.empty())Q.pop();
			break;
		}

		for (int i = 0; i < 8; i++)
		{
			int nx = QX + dx[i];
			int ny = QY + dy[i];

			if ((nx >= 0) && (ny >= 0) && (nx < D) && (ny < D) && !visited[nx][ny])
			{
				Q.push(make_pair(nx, ny));
				visited[nx][ny] = true; 
				arr[nx][ny] = arr[QX][QY] + 1;

			}

		}
	}


}

int main()
{ 
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	
	 
	cin >> M; 
	for (int i = 0; i < M; i++)
	{
		cin >> D;
		cin >> cur.first >> cur.second;
		cin >> target.first >> target.second;

		BFS(cur.first, cur.second);
		reset();
	}


	return 0;
}