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

문제

 

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 몇 번만에 이동할 수 있는지 출력한다.

 

---

 

풀이

 

이 문제 역시 bfs를 이용하면 간단하게 해결할 수 있다.

 

달라진 점은 기존 문제에서는 상하좌우 네 방향을 움직였지만, 나이트의 경우에는 8가지 방향으로 움직인다는 점이다.

---

 

코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int N;
int x, y; // 처음 위치
int gx, gy; // goal X, goal Y

int visit[300][300] = { 0, };
int dir[8][2] = { {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1} };

void bfs();

int main() {
	int test_case;

	cin >> test_case;

	for (int t = 0; t < test_case; t++) {
		cin >> N;

		cin >> x >> y >> gx >> gy;

		bfs();

		cout << visit[gy][gx] << "\n";
		memset(visit, 0, sizeof(visit));
	}
}

void bfs() {
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));

	while (!q.empty()) {
		int curX = q.front().first;
		int curY = q.front().second;

		if (curX == gx && curY == gy)
			break;

		q.pop();

		for (int i = 0; i < 8; i++) {
			int nextX = curX + dir[i][0];
			int nextY = curY + dir[i][1];

			if (0 <= nextX && nextX < N && 0 <= nextY && nextY < N) {
				if (visit[nextY][nextX] == 0) {
					visit[nextY][nextX] = visit[curY][curX] + 1;
					q.push(make_pair(nextX, nextY));
				}
			}
		}
	}
}