[C++] 7562 : 나이트의 이동

📝 문제

7562 : 나이트의 이동

💭 문제해결법

나이트의 움직임이 8방향인것을 고려해서 10시 방향부터 차례대로 움직이게 하고,
나이트의 다음 움직임이 나이트의 목적지와 같을때 ans에다 현재 dist에 들어가있는 값에서 + 1를 해주고,
큐값을 비워서 반복되지 않게 한다.
BFS가 종료된후 초기화와 동시에 출력한다.

✏️ 입력

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

💻 출력

5
28
0

⌨️ 소스코드

//7562 나이트의 이동

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
#define X first
#define Y second

int t; //테스트 케이스 개수
int n; //체스판 한변의 길이
int x, y; //초기 나이트 위치
int goal_x, goal_y; //나이트의 목적지
int ans = 0;
queue<pair<int, int>> que;
int dist[302][302];
int vis[302][302];
int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

void bfs(int x, int y) {
	que.push({ x, y });
	vis[x][y] = 1;
	while (!que.empty()) {
		pair<int, int> cur = que.front(); que.pop();
		for (int dir = 0; dir < 8; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (vis[nx][ny] == 1) continue;
			if (nx == goal_x && ny == goal_y) {
				ans = dist[cur.X][cur.Y] + 1;
				while (!que.empty()) que.pop();
				break;
			}
			vis[nx][ny] = 1;
			que.push({ nx, ny });
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
		}
	}
}

void init_print() {
	cout << ans << "\n";
	ans = 0;

	for (int j = 0; j < n; j++) { //방문기록 초기화, 보드 초기화
		fill(vis[j], vis[j] + n, 0);
		fill(dist[j], dist[j] + n, 0);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		cin >> x >> y;
		cin >> goal_x >> goal_y;

		bfs(x, y);
		init_print();
	}
}