c++ 백준_1600_"말이 되고픈 원숭이"

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

1600번: 말이 되고픈 원숭이

 

개인적으로 나한테 좀 어려웠다고 느낀다.

​

​

처음 접근은 말과 원숭이의 움직임으로 방문한 좌표를

visit, k_visit 두개로 나눠 따로 방문 체크를 하였다.

​

이렇게 하면 말의 움직임 1~2번 정도만 가능하였다.

​

그래서 처음으로 3차원 배열을 사용하였다.

각 층은 말의 움직임을 몇번 사용하고 방문했느냐다.

​

그냥 생각하다가 그려보고싶었다 헿

​

​

근데 그렇게 하더라도 약간 의문이 생겼다.

말의 움직임이 방문한 곳에 원숭이가 방문을 하고싶다면?

​

그건 어짜피 최소를 구하니까 말이 방문했다면

최소한 원숭이는 방문 못하는 곳이거나

원숭이보다 방문을 먼저 할 수 있어 움직임을 최소화할 수 있다.

​

​

살펴봤던 예시로

​

말 움직임 start : S

end : E

​

case 1

case 2

case 1의 경우 E 오른쪽 좌표가 원숭이 움직임으로 방문됐다고 체크 될 것이다.

case 2의 경우 말의 움직임으로 E 좌표를 방문을 해야되는데 원숭이가 방문했다고 체크 되면

방문을 못하게된다.

​

근데 BFS 특성상 최종좌표에 먼저 도달하게되면 그게 즉 최소 거리가 되니

크게 상관없던 것이였다.

​

괜한 생각을 많이했다.

 

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

pair<int, int> horse_move[] = { {-1,-2},{-2,-1},{-2,1},{-1,2},
			{1,2},{2,1},{2,-1},{1,-2} };
pair<int, int> monkey_move[] = { {-1,0},{0,1},{1,0},{0,-1} };

int K;
int W, H;
int board[201][201];
bool k_visit[201][201][31];

typedef struct {
	int x, y;
	int k_cnt;
	int cnt;
}node;

bool is_in(int x, int y) {
	if (x < 0 || y < 0 || x >= H || y >= W || board[x][y] == 1)
		return false;
	return true;
}

void BFS() {

	queue<node> q;


	node e;
	e = { 0,0,0,0 };
	q.push(e);

	int ans = -1;

	k_visit[0][0][0] = true;
	
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int k_cnt = q.front().k_cnt;
		int cnt = q.front().cnt;
		q.pop();

		if (x == H - 1 && y == W - 1) {
			ans = cnt;
			break;
		}

		for (int i = 0; i < 4; i++) {
			int dx = monkey_move[i].first;
			int dy = monkey_move[i].second;

			if (is_in(x + dx, y + dy)) {
				if (!k_visit[x + dx][y + dy][k_cnt]) {
					e = { x + dx,y + dy,k_cnt,cnt + 1 };
					q.push(e);
					k_visit[x + dx][y + dy][k_cnt] = true;
				}
			}
		}

		if (k_cnt < K) {
			for (int i = 0; i < 8; i++) {
				int dx = horse_move[i].first;
				int dy = horse_move[i].second;

				if (is_in(x + dx, y + dy)) {
					if (!k_visit[x + dx][y + dy][k_cnt + 1]) {
						e = { x + dx,y + dy,k_cnt + 1,cnt + 1 };
						q.push(e);
						k_visit[x + dx][y + dy][k_cnt + 1] = true;
					}
				}
			}
		}

		

	}
	
	cout << ans;
}

int main(void) {


	cin >> K;
	cin >> W >> H;

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> board[i][j];
		}
	}


	BFS();

}