백준 7562번: 나이트의 이동

[문제 링크]

7562번: 나이트의 이동

---

나이트의 위치를 시작점으로 하는 너비 우선 탐색을 통해 간단히 풀 수 있다.

나이트가 도착지점에 도달했을 때 그동안 움직인 횟수를 반환하도록 구현하였다.

---

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

struct Pos {
	int y;
	int x;
};
bool operator== (const Pos& rhs, const Pos& lhs) {
	if (rhs.y == lhs.y && rhs.x == lhs.x) return true;
	else return false;
}

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

int bfs(Pos night, Pos dest) {
	memset(visited, false, sizeof(visited));

	queue<pair<Pos, int>> q;
	q.push({ night, 0 });
	visited[night.y][night.x] = true;

	while (!q.empty()) {
		Pos here = q.front().first;
		int move = q.front().second;
		q.pop();

		if (here == dest) return move;

		for (int i = 0; i < 8; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };
			int nextMove = move + 1;
			
			if (there.y >= 0 && there.y < I && there.x >= 0 && there.x < I) 
				if (!visited[there.y][there.x]) {
					visited[there.y][there.x] = true;
					q.push({ there, nextMove });
				}
		}
	}
}
int main(void) {
	int tc;
	cin >> tc;

	Pos night, destination;
	while (tc--) {
		cin >> I;
		cin >> night.y >> night.x;
		cin >> destination.y >> destination.x;

		cout << bfs(night, destination) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 166 day