[백준][16959][c++] 체스판 여행 1

체스판 여행 1

[내 풀이]
나이트, 비숍, 룩을 이동시키거나 말의 종류를 바꾸는 것을 매 초마다 하는 것이다. 매초마다 나올 수 있는 경우가 생기고 N* N까지의 최단 시간을 찾아야 하기 때문에 BFS로 풀 수 있다고 생각했다. BFS에서 시간을 줄여주는 중복처리에 경우 4차원 배열로 y좌표, x 좌표, 출발 체스판 번호, 말의 종류로 놓았다.

[코드]

#include <iostream>
#include <queue>
#define N_MAX 11

using namespace std;

int N;
pair<int, int> start;
int map[N_MAX][N_MAX];
bool visited[N_MAX][N_MAX][N_MAX*N_MAX][3] = {false,};   //y 좌표, x 좌표, 체스판 번호, 말 종류
int dir_knight_y[8] = { -2,-1,1,2,2,1,-1,-2 };
int dir_knight_x[8] = { 1,2,2,1,-1,-2,-2,-1 };  //나이트의 움직임 
int dir_bishop_y[4] = { -1,1,1,-1 };
int dir_bishop_x[4] = { 1,1,-1,-1 };            //비숍의 움직임
int dir_look_y[4] = { 0,0,1,-1 };
int dir_look_x[4] = { 1,-1,0,0 };               //룩의 움직임

struct info {
	int y;
	int x;
	int mal;    // 말 종류: 0 == 나이트, 1 == 비숍, 2 == 룩
	int cost = 0; //걸린 시간
	int departure;  //출발한 체스판 번호

	info(int _y, int _x, int _mal, int _cost, int _departure): y(_y), x(_x),mal(_mal), cost(_cost), departure(_departure) {};
};


bool check_range(int y, int x) {
	//좌표를 벗어나지 않았는지
	if (y < 0 || y >= N || x < 0 || x >= N) return false;
	return true;
}

int solve() {
	int ans = -1;
	queue<info> q;
	//1에 다가 비숍, 나이트, 룩 다 넣음
	q.push(info(start.first, start.second, 0, 0, 1));
	q.push(info(start.first, start.second, 1, 0, 1));
	q.push(info(start.first, start.second, 2, 0, 1));
	visited[start.first][start.second][1][0] = true;
	visited[start.first][start.second][1][1] = true;
	visited[start.first][start.second][1][2] = true;

	while (!q.empty()) {
		info cur = q.front();
		q.pop();
		
		if (cur.departure == N * N) {
			//도착해야 하는 곳에 도착했을 시
			if (ans == -1 || ans > cur.cost) ans = cur.cost;
		}

		if (cur.mal == 0) {
			//나이트
			for (int dir = 0; dir < 8; dir++) {
				int new_y = cur.y + dir_knight_y[dir];
				int new_x = cur.x + dir_knight_x[dir];
				int depature = cur.departure;

				if (!check_range(new_y, new_x)) continue;
				if (cur.departure + 1 == map[new_y][new_x]) {
					depature += 1;
				}
				if (visited[new_y][new_x][depature][cur.mal]) continue;
				visited[new_y][new_x][depature][cur.mal] = true;
				q.push(info(new_y, new_x, cur.mal, cur.cost + 1, depature));
			}
		}
		else if (cur.mal == 1) {
			//비숍
			for (int dir = 0; dir < 4; dir++) {
				for (int k = 1; k < N; k++) {
					//비숍에 경우 대각선으로 무한정으로 움직일 수 있음
					int new_y = cur.y + dir_bishop_y[dir]*k;
					int new_x = cur.x + dir_bishop_x[dir]*k;
					int depature = cur.departure;
					if (!check_range(new_y, new_x)) break;
					if (cur.departure + 1 == map[new_y][new_x]) {
						depature += 1;
					}
					if (visited[new_y][new_x][depature][cur.mal]) continue;
					visited[new_y][new_x][depature][cur.mal] = true;
					q.push(info(new_y, new_x, cur.mal, cur.cost + 1, depature));

				}
				
			}
		}
		else if (cur.mal == 2) {
			//룩
			for (int dir = 0; dir < 4; dir++) {
				for (int k = 1; k < N; k++) {
					//룩에 경우 사방향으로 무한정으로 움직일 수 있음
					int new_y = cur.y + dir_look_y[dir]*k;
					int new_x = cur.x + dir_look_x[dir]*k;
					int depature = cur.departure;

					if (!check_range(new_y, new_x)) break;
					if (cur.departure + 1 == map[new_y][new_x]) {
						depature += 1;
					}
					if (visited[new_y][new_x][depature][cur.mal]) continue;
					visited[new_y][new_x][depature][cur.mal] = true;
					q.push(info(new_y, new_x, cur.mal, cur.cost + 1, depature));
				}
				
			}
		}

		for (int ch_mal = 0; ch_mal < 3; ch_mal++) {
			//체스판에 있는 말을 변경할 시
			if (ch_mal == cur.mal) continue;
			if (visited[cur.y][cur.x][cur.departure][ch_mal]) continue;
			visited[cur.y][cur.x][cur.departure][ch_mal] = true;
			q.push(info(cur.y, cur.x, ch_mal, cur.cost + 1, cur.departure));
		}
	}
	return ans;

}


int main() {
	cin >> N;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
			if (map[y][x] == 1) {
				start.first = y;
				start.second = x;
			}
		}
	}
	int answer = solve();
	cout << answer << "\n";
}

[총평]
비숍이랑 룩의 가능한 움직임을 한칸으로만 봐서 오래 걸렸다...