백준 7562 c++ "나이트의 이동" -[PlusUltraCode]

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

7562번: 나이트의 이동

[필자 사고]

이 문제는 BFS 너비우선 탐색 및 최단거리를 합쳐 놓은 문제이다. 

 

대부분의 2차원 배열에서의 이동경로는 상 하 좌 우 만 있었지만.

 

공식처럼 외운 사람은 나이트의 이동 경로를 어떻게 코드로 짜는지 모를 수 있다.

 

약간의 팁이 있다면 공식처럼 외우지 말고 나이트가 이동할 수 있는 모든 경우의 수를 dx와dy에 순서대로 저장해 놓는다라고 생각하면 쉽게 작성할 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> Node;

int dx[8] = { 2,1,-1,-2,-2,-1,1,2 };
int dy[8] = { 1,2,2,1,-1,-2,-2,-1 };

vector<vector<int>> Arr;
vector<vector<bool>> visited;
int N;
int sero1, sero2, garo1, garo2;
void Input() {
	vector<vector<int>> Arr2;
	vector<vector<bool>> visited2;
	cin >> N;
	Arr2.resize(N);
	visited2.resize(N);
	for (int i = 0; i < N; i++) {
		Arr2[i].resize(N);
		visited2[i].resize(N, false);
	}
	cin >> sero1 >> garo1;
	cin >> sero2 >> garo2;
	
	Arr = Arr2;
	visited = visited2;
}
bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < N)return true;
	return false;
}
void BFS() {
	queue<Node> myQueue;
	myQueue.push({ sero1, garo1 });
	visited[sero1][garo1] = true;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		if (nowSero == sero2 && nowGaro == garo2) {
			cout << Arr[nowSero][nowGaro];
			return;
		}
		myQueue.pop();
		for (int i = 0; i < 8; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			if (Inside(nextSero, nextGaro) &&
				visited[nextSero][nextGaro] == false) {
				visited[nextSero][nextGaro] = true;
				myQueue.push({ nextSero,nextGaro });
				Arr[nextSero][nextGaro] = Arr[nowSero][nowGaro] + 1;
			}
		}
	}

}

int main(void) {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		Input();
		BFS();
		cout << '\n';
	}
}