[백준] 16948번. 데스 나이트

[백준] 16948번. 데스 나이트

1. 문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

2. 입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

3. 출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

4. 풀이

• 나이트의 이동 문제를 참고했다.
• 나이트의 이동과 기본적으로 똑같고 이동 방향만 조금 다르기 때문에 dx와 dy만 수정했다.

5. 처음 코드와 달라진 점

• 이동하는 경우의 수가 달라져 loop 조건을 변경해주어야 하는데 안 했다.

6. 코드

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

int map[200][200];
bool visited[200][200];

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

int bfs(int n, int x, int y, int target_x, int target_y) {
	map[x][y] = 0;
	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[x][y] = true;

	while (!q.empty()) {
		int current_x = q.front().first;
		int current_y = q.front().second;
		q.pop();

		for (int i = 0; i < 6; i++) {
			int nx = current_x + dx[i];
			int ny = current_y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (!visited[nx][ny]) {
				visited[nx][ny] = true;
				map[nx][ny] = map[current_x][current_y] + 1;
				q.push({ nx, ny });
			}
		}
	}
	return map[target_x][target_y] == 0 ? -1 : map[target_x][target_y];
}

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


	int n;
	cin >> n;

	int current_x, current_y, target_x, target_y;
	cin >> current_x >> current_y >> target_x >> target_y;

	cout << bfs(n, current_x, current_y, target_x, target_y) << "\n";
}