[백준/BOJ] 백준 7562번 : 나이트의 이동

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

7562번: 나이트의 이동

시작 위치에서 목표 위치에 도달할 때까지 bfs를 진행한다. 목표 위치에 도착했을 때 그 목표 위치의 depth가 시작 위치에서 목표 위치로 이동할 수 있는 최소 이동 거리이다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

int len;
int dx_dy[8][2] = { {-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2} };
int discoverd[300][300];
int depth[300][300];

int Solve(pair<int, int> start, pair<int, int> stop)
{
	//시작지점을 발견표시하고, 시작지점의 깊이를 0으로 한다
	discoverd[start.first][start.second] = 1;
	depth[start.first][start.second] = 0;

	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//도착지점에 도착 했을때 그 깊이가 도착지점으로 이동할 수 있는 최소 이동 거리이다
		if (here.first == stop.first && here.second == stop.second)
			return depth[here.first][here.second];

		//이동할 수 있는곳을 확인한다
		for (int i = 0; i < 8; i++)
		{
			pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
			if (there.first >= 0 && there.first < len && there.second >= 0 && there.second < len && discoverd[there.first][there.second] == 0)
			{
				discoverd[there.first][there.second] = 1;
				depth[there.first][there.second] = depth[here.first][here.second] + 1;
				q.push(there);
			}
		}
	}

	//도착지점에 도착할 수 없을때
	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int testcase;
	pair<int, int> start;
	pair<int, int> stop;
	int temp1, temp2, temp3, temp4;

	cin >> testcase;

	for (int t = 0; t < testcase; t++)
	{
		memset(discoverd, 0, sizeof(discoverd));
		memset(depth, 0, sizeof(depth));

		cin >> len;
		cin >> temp1 >> temp2 >> temp3 >> temp4;

		start = make_pair(temp1, temp2);
		stop = make_pair(temp3, temp4);

		cout << Solve(start, stop) << "\n";
	}

	return 0;
}