[백준] 7562번 나이트의 이동

7562번: 나이트의 이동

출발 위치에서부터 나이트가 갈 수 있는 8가지 위치의 값에

현재 위치의 값 +1을 넣어주고 (방문하지 않은 경우에만)

이 위치들을 큐에 넣어준다.

그렇게 큐의 front마다 탐색해주다 목표 위치를 만나게 되면 그만두고 출력시킨다.

#include <iostream>
#include <queue>
using namespace std;
int dx[8] = { -1, -2, -2, -1, 1, 2, 2, 1 }, dy[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int a, b, x, y, finish = 0;

void Bfs(int X, int Y, int L, int res[][301], int visited[][301], queue<pair<int, int>> q) {
	while (1) {
		if ((a == X && b == Y) || finish == 1) break;
		for (int i = 0; i < 8; i++) {
			x = a + dx[i], y = b + dy[i];
			if (x >= 0 && x < L && y >= 0 && y < L && visited[x][y] == 0) {
				res[x][y] = res[a][b] + 1;
				visited[x][y] = 1;
				q.push(pair<int, int>(x, y));
			}
			if (x == X && y == Y) {
				finish = 1;
				break;
			}
		}
		q.pop();
		a = q.front().first, b = q.front().second;
	}
	
}

int main() {
	int T, L, X, Y;
	cin >> T;
	for (int t = 0; t < T; t++) {
		finish = 0;
		int res[301][301] = { 0 }, visited[301][301] = { 0 };
		cin >> L >> a >> b >> X >> Y;
		visited[a][b] = 1;
		queue <pair<int, int>> q;
		q.push(pair<int, int>(a, b));
		Bfs(X, Y, L, res, visited, q);
		cout << res[X][Y] << "\n";
	}
	return 0;
}