[백준/BOJ/16959] 체스판 여행1

드러운 문제다.

 

bfs 에 4가지 경우를 넣는다.

1. 체스말 교체

2. 룩의 모든 경우의 수

3. 나이트의 모든 경우의 수

4. 비숍의 모든 경우의 수

 

그리고 num == N*N-1 은, map 에 쓰인 값을 -1 로 처리 했기 때문에 N*N 이 아닌 N*N -1 이 최종 지점이고,

최종 지점에서는 더 할게 없기 때문에 저렇게 처리한다.

#include <iostream>
#include <cstring>
#include <tuple>
#include <queue>
using namespace std;
typedef tuple<int, int, int, int> tp;
const int dx1[] = { -2,-1,1,2,2,1,-1,-2 };
const int dy1[] = { 1,2,2,1,-1,-2,-2,-1 };
const int dx2[] = { 0,0,1,-1 };
const int dy2[] = { 1,-1,0,0 };
const int dx3[] = { 1,1,-1,-1 };
const int dy3[] = { 1,-1,1,-1 };
int N, map[11][11], dp[11][11][101][4];
queue<tp> q;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			map[i][j] -= 1;
			if (map[i][j] == 0) {
				for (int k = 0; k < 3; k++) {
					dp[i][j][0][k] = 0;
					q.push({ i,j,0,k });
				}
			}
		}
	}
	int res = -1;
	while (!q.empty()) {
		int x, y, num, piece;
		tie(x, y, num, piece) = q.front(); q.pop();
		if (num == N * N -1) { // 끝에 도달, 더 할게 없다.
			if (res == -1 || res > dp[x][y][num][piece]) {
				res = dp[x][y][num][piece];
			}
		}
		for (int i = 0; i < 3; i++) {
			if (piece == i) continue;
			if (dp[x][y][num][i] == -1) {
				dp[x][y][num][i] = dp[x][y][num][piece] + 1;
				q.push({ x,y,num,i });
				// 교체
			}
		}
		if (piece == 0) {
			for (int i = 0; i < 8; i++) {
				int nx = x + dx1[i];
				int ny = y + dy1[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < N) {
					int next = num;
					if (map[nx][ny] == num + 1) {
						next = num + 1;
					}
					if (dp[nx][ny][next][piece] == -1) {
						dp[nx][ny][next][piece] = dp[x][y][num][piece] + 1;
						q.push({ nx,ny,next,piece });
					}
				}
			}
		}
		else if (piece == 1) {
			for (int i = 0; i < 4; i++) {
				for (int l = 1;; l++) {
					int nx = x + dx2[i] * l;
					int ny = y + dy2[i] * l;
					if (0 <= nx && nx < N && 0 <= ny && ny < N) {
						int next = num;
						if (map[nx][ny] == num + 1) {
							next = num + 1;
						}
						if (dp[nx][ny][next][piece] == -1) {
							dp[nx][ny][next][piece] = dp[x][y][num][piece] + 1;
							q.push({ nx,ny,next,piece });
						}
					}
					else {
						break;
					}
				}
			}
		}
		else {
			for (int i = 0; i < 4; i++) {
				for (int l = 1;; l++) {
					int nx = x + dx3[i] * l;
					int ny = y + dy3[i] * l;
					if (0 <= nx && nx < N && 0 <= ny && ny < N) {
						int next = num;
						if (map[nx][ny] == num + 1) {
							next = num + 1;
						}
						if (dp[nx][ny][next][piece] == -1) {
							dp[nx][ny][next][piece] = dp[x][y][num][piece] + 1;
							q.push({ nx,ny,next,piece });
						}
					}
					else {
						break;
					}
				}
			}
		}
	}
	cout << res << "\n";
	return 0;
}