백준 7562번 나이트의 이동 C++

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

 

나이트의 이동 범위를 저장해놓은 배열을 이용해서 bfs방식을 통해 문제를 해결하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int posR[8] = { -2,-1,1,2,2,1,-1,-2 };
int posC[8] = { 1,2,2,1,-1,-2,-2,-1 };

int bfs(int n, pair<int, int> start, pair<int, int> target) {
	vector<vector<bool>> visited(n, vector<bool>(n, false));
	queue<pair<pair<int, int>, int>> q;
	q.push({ start,0 });
	visited[start.first][start.second] = true;
	int ret;
	while (!q.empty()) {
		auto curr = q.front();
		q.pop();
		if (curr.first == target) {
			ret = curr.second;
			break;
		}
		for (int i = 0; i < 8; i++) {
			int nextRow = curr.first.first + posR[i];
			int nextCol = curr.first.second + posC[i];
			if (nextRow < 0 || nextRow >= n) continue;
			if (nextCol < 0 || nextCol >= n) continue;
			if (visited[nextRow][nextCol]) continue;
			visited[nextRow][nextCol] = true;
			q.push({ {nextRow,nextCol},curr.second + 1 });
		}
	}
	return ret;
}

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

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		pair<int, int> currPos;
		pair<int, int> targetPos;
		cin >> currPos.first >> currPos.second;
		cin >> targetPos.first >> targetPos.second;
		int ans = bfs(n, currPos, targetPos);
		cout << ans << "\n";
	}
};