백준 16948번 데스 나이트 C++

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

일반적인 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;

struct Knight {
	Knight(int row, int col, int moveCount) :row(row), col(col), moveCount(moveCount) {}
	int row;
	int col;
	int moveCount;
};

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

	int dirR[6] = { -2,-2,0,2,2,0 };
	int dirC[6] = { -1,1,2,1,-1,-2 };

	int n;
	cin >> n;
	vector<vector<bool>> found(n, vector<bool>(n, false));
	int r1, c1, r2, c2;
	cin >> r1 >> c1 >> r2 >> c2;
	queue<Knight> q;
	q.push(Knight(r1, c1, 0));
	found[r1][c1] = true;
	int ans = -1;
	while (!q.empty()) {
		auto a = q.front();
		q.pop();
		if (a.row == r2 && a.col == c2) {
			ans = a.moveCount;
			break;
		}
		for (int i = 0; i < 6; i++) {
			int nextRow = a.row + dirR[i];
			int nextCol = a.col + dirC[i];
			if (nextRow < 0 || nextRow >= n) continue;
			if (nextCol < 0 || nextCol >= n) continue;
			if (found[nextRow][nextCol]) continue;
			q.push(Knight(nextRow, nextCol, a.moveCount + 1));
			found[nextRow][nextCol] = true;
		}
	}
	cout << ans;
};