(c++)백준 1600번: 말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

[풀이]

bfs를 사용하여 풀었다.

말처럼 이동한 횟수가 K번 미만이면 말처럼 이동한 칸을 queue에 넣는다. 그리고 원숭이로 이동하는 경우 또한 queue에 넣어야한다.

 

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

struct Monkey {
	int x, y;
	int horse;//말 방식으로 이동한 횟수
	int dist;//해당 칸까지 이동한 횟수
};

int K, W, H;
int Map[200][200];
bool visited[200][200][31];
const int dhorse[][2] = { {-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2} };
const int dmonkey[][2] = { {-1,0},{1,0},{0,-1},{0,1} };

int bfs() {
	queue<Monkey>q;
	q.push({ 0,0,0,0 });
	visited[0][0][0] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int horse = q.front().horse;
		int dist = q.front().dist;
		q.pop();
		if (x == H - 1 && y == W - 1) {
			return dist;
		}
		//말의 움직임으로 움직이는 경우
		if (horse < K) {
			for (int i = 0; i < 8; i++) {
				int nx = x + dhorse[i][0];
				int ny = y + dhorse[i][1];
				if (nx < 0 || nx >= H || ny < 0 || ny >= W)
					continue;
				if (Map[nx][ny] == 0 && visited[nx][ny][horse + 1] == false) {
					visited[nx][ny][horse + 1] = true;
					q.push({ nx,ny,horse + 1,dist + 1 });
				}
			}
		}
		//원숭이의 움직임으로 움직이는 경우
		for (int i = 0; i < 4; i++) {
			int nx = x + dmonkey[i][0];
			int ny = y + dmonkey[i][1];
			if (nx < 0 || nx >= H || ny < 0 || ny >= W)
				continue;
			if (Map[nx][ny] == 0 && visited[nx][ny][horse] == false) {
				visited[nx][ny][horse] = true;
				q.push({ nx,ny,horse,dist + 1 });
			}
		}
	}
	return -1;
}

int main() {
	cin >> K >> W >> H;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> Map[i][j];
		}
	}
	int res = bfs();
	cout << res << '\n';
	return 0;
}