16948_데스 나이트

▶ 실버 1 (BFS)

풀이

BFS를 이용하는 문제이다.

먼저 이동할 수 있는 경우와 없는 경우를 구분하였다. (bfs를 돌리면서 이동할 수 없는지 확인할수는 없기 때문에 미리 거르는 방식으로)

규칙을 찾아보니

1) x좌표(= r) 가 2의 배수인 경우, y좌표(= c)는 2k + 1이 성립.

2) x좌표(= r) 가 4의 배수인 경우, y좌표(= c)는 2k 이 성립.

인 것이 보였다.

이 때, 2의 배수는 4의 배수를 포함하고 있으므로 4의 배수일 경우부터 걸러야 한다.

	// 도착 불가인지 확인
	int tmp1 = abs(r1 - r2);
	int tmp2 = abs(c1 - c2);
	if (tmp1 % 4 == 0) {
		if (tmp2 % 2 == 0) {
			ans = bfs(r1, c1, r2, c2);
		}
		else {
			ans = -1;
		}
	}
	else if (tmp1 % 2 == 0) {
		if ((tmp2 - 1) % 2 == 0) {
			ans = bfs(r1, c1, r2, c2);
		}
		else {
			ans = -1;
		}
	}
	else {
		ans = -1;
	}

 

다음과 같이 규칙에 해당하면 bfs를 돌리고, 아니라면 -1를 할당했다.

 

다음으로 BFS를 구현해야 하는데, 최대한 경우의 수를 줄이고 싶어서 보니 사분면을 기준으로 경우의 수를 나눌 수 있었다.

현재 좌표에서 도착지점을 뺐을 때,

(+, +)  -> 1사분면

(-, +) -> 2사분면

(-, -) -> 3사분면

(+, -) -> 4사분면

각각 해당하는 경우만 큐에 삽입했다. (모든 경우에는 0이 포함된다)

 

또 생각해야 할 경우는 1) 이동할 지점이 체스판 범위 내여야 하며 2) 방문하지 않은 점이어햐 한다는 점이다.

 

자료구조는 지점을 삽입할 이중 pair queue, 방문 기록을 할 2차원 배열을 사용하였다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <set>
#include <queue>
#include <vector>
#include <ctime>
#include <algorithm>
#define MAX 201
using namespace std;

queue<pair<pair<int, int>, int>> q;
int n;
bool visited[MAX][MAX];

int bfs(int a, int b, int x, int y) {
	q.push({ {a, b}, 0 });
	visited[a][b] = true;
	while (!q.empty()) {
		int t1 = q.front().first.first; // 현재 위치 r좌표
		int t2 = q.front().first.second; // 현재 위치 c좌표
		int sec = q.front().second;
		q.pop();

		// 현재위치가 도착지점과 같을 때
		if (t1 == x && t2 == y) {
			return sec;
		}
		// 현재위치와 도착지점의 차를 구한다.
		int sub1 = t1 - x;
		int sub2 = t2 - y;

		// 체스판 범위 내에서 && 도착지점과 같은 사분면에 존재하면서 && 방문하지 않은 점일 경우
		//(r - 2, c - 1)
		if (t1 - 2 >= 0 && t2 - 1 >= 0 && sub1 >= 0 && sub2 >= 0 && !visited[t1 - 2][t2 - 1]) {
			q.push({ {t1 - 2, t2 - 1}, sec + 1 });
			visited[t1 - 2][t2 - 1] = true;
		}
		//(r - 2, c + 1)
		if (t1 - 2 >= 0 && t2 + 1 < n && sub1 >= 0 && sub2 <= 0 && !visited[t1 - 2][t2 + 1]) {
			q.push({ {t1 - 2, t2 + 1}, sec + 1 });
			visited[t1 - 2][t2 + 1] = true;
		}
		//(r, c - 2)
		if (t2 - 2 >= 0 && sub2 >= 0 && !visited[t1][t2 - 2]) {
			q.push({ {t1, t2 - 2}, sec + 1 });
			visited[t1][t2 - 2] = true;
		}
		//(r, c + 2)
		if (t2 + 2 < n && sub2 <= 0 && !visited[t1][t2 + 2]) {
			q.push({ {t1, t2 + 2}, sec + 1 });
			visited[t1][t2 + 2] = true;
		}
		//(r + 2, c - 1)
		if (t1 + 2 < n && t2 - 1 >= 0 && sub1 <= 0 && sub2 >= 0 && !visited[t1 + 2][t2 - 1]) {
			q.push({ {t1 + 2, t2 - 1}, sec + 1 });
			visited[t1 + 2][t2 - 1] = true;
		}
		//(r + 2, c + 1)
		if (t1 + 2 < n && t2 + 1 < n && sub1 <= 0 && sub2 <= 0 && !visited[t1 + 2][t2 + 1]) {
			q.push({ {t1 + 2, t2 + 1}, sec + 1 });
			visited[t1 + 2][t2 + 1] = true;
		}
	}
}

int main() {
	cin >> n;
	int r1, c1; // 출발점
	int r2, c2; // 도착점
	int ans = 0; // 소요시간
	cin >> r1 >> c1 >> r2 >> c2;

	// 도착 불가인지 확인
	int tmp1 = abs(r1 - r2);
	int tmp2 = abs(c1 - c2);
	if (tmp1 % 4 == 0) {
		if (tmp2 % 2 == 0) {
			ans = bfs(r1, c1, r2, c2);
		}
		else {
			ans = -1;
		}
	}
	else if (tmp1 % 2 == 0) {
		if ((tmp2 - 1) % 2 == 0) {
			ans = bfs(r1, c1, r2, c2);
		}
		else {
			ans = -1;
		}
	}
	else {
		ans = -1;
	}
	cout << ans << endl;
	return 0;
}