[BOJ] 1600 - 말이 되고픈 원숭이

문제 : https://www.acmicpc.net/problem/1600

---

[알고리즘풀이]

우선, BFS 탐색입니다. 하지만 방문한 지점을 일반적인 2차원 배열로 check 한다면 문제를 해결할 수 없습니다.

(x, y) 지점에 말처럼 i 번 뛰어서 도착한 것과, j 번 ( i ≠ j ) 뛰어서 도착한 것은 다른 경우의 수이기 때문입니다.

따라서, (x, y) 지점에 말처럼 i 번 뛰어서 도착한 적이 있다고, j 번 뛰어서 도착한 경우를 탐색 안 하면 안 됩니다.

즉,  visited를 3차원 배열로 check 해줘야 합니다.

 

bool map[x][y] : (x, y) 지점이 갈 수 있는 곳인가 아닌가.

bool cmap[x][y][k] : (x, y) 지점에 k번 말처럼 뛰어서 도착한 적이 있는가.

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

queue<pair<int, int>> P, L;
int k, w, h;
bool map[200][200], cmap[200][200][30];
bool flag = true;
int h_x[8] = { -1,-2,-2,-1,1,2,2,1 };
int h_y[8] = { -2,-1,1,2,-2,-1,1,2 };
int d_x[4] = { -1, 0, 1, 0 };
int d_y[4] = { 0, -1, 0, 1 };

bool check(int x, int y) {
	if (0 <= x && x < w && 0 <= y && y < h)
		return true;
	return false;
}

void BFS() {
	P.push(make_pair(0,0));
	L.push(make_pair(0,0));

	while (!P.empty()) {
		pair<int, int> p = P.front(), l = L.front();
		P.pop(), L.pop();

		int x = p.first, y = p.second, length = l.first, horse = l.second;

		if (x == w - 1 && y == h - 1) {
			flag = false;
			cout << length;
			break;
		}

		int s_x, s_y;
		if (horse < k) {
			for (int i = 0; i < 8; i++) {
				s_x = x + h_x[i];
				s_y = y + h_y[i];
				if (check(s_x, s_y) && map[s_x][s_y] == 0 && cmap[s_x][s_y][horse + 1] != 1 ) {
					P.push(make_pair(s_x, s_y));
					L.push(make_pair(length + 1, horse + 1));
					cmap[s_x][s_y][horse + 1] = 1;
				}
			}
		}
		for (int i = 0; i < 4; i++) {
			s_x = x + d_x[i];
			s_y = y + d_y[i];
			if (check(s_x, s_y) && map[s_x][s_y] == 0 && cmap[s_x][s_y][horse] != 1) {
				P.push(make_pair(s_x, s_y));
				L.push(make_pair(length + 1, horse));
				cmap[s_x][s_y][horse] = 1;
			}
		}
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> k >> h >> w;

	for (int i = 0; i < w; i++)
		for (int j = 0; j < h; j++)
			cin >> map[i][j];
	
	BFS();
	
	if (flag)
		cout << -1;
}

visited 배열을 3차원 배열로 만들면 금방 해결할 수 있지만, 3차원 배열로 생각하기가 어려웠다.

---