[백준/C++] 1600번 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

 

 

문제풀이

 

BFS 알고리즘 문제이다.

 

백준 2206번인 벽 부수고 이동하기 문제와 상당히 유사하다. 다른 점은 2206번은 능력을 한 번만 쓸 수 있지만 1600번은 능력을 K번 쓸 수 있다. 때문에  3차원 dist 배열을 K+1개만큼 선언해야 한다.

 

 

코드

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;


int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int hx[8] = {-2,-2,-1,-1,1,1,2,2}; //말의 움직임
int hy[8] = {1,-1,2,-2,2,-2,1,-1};

int board[200][200];
int dist[200][200][31];

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

	int k,w,h;
	cin>>k>>w>>h;
	
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			cin>>board[i][j];
		}
	}

	queue<tuple<int,int,int>> q;
	q.push(make_tuple(0,0,k));
	dist[0][0][k] = 1;

	while(!q.empty()){
		tuple<int,int,int> cur = q.front();
		q.pop();

		if(get<0>(cur) == h-1 && get<1>(cur) == w-1){
			cout<<dist[get<0>(cur)][get<1>(cur)][get<2>(cur)]-1;
			return 0;
		}

		if(get<2>(cur) >=  1){
			for(int dir=0; dir<8; dir++){
				int nx = get<0>(cur) + hx[dir];
				int ny = get<1>(cur) + hy[dir];
				int nk = get<2>(cur) - 1;

				if(nx<0||nx>=h||ny<0||ny>=w) continue;
				if(dist[nx][ny][nk] || board[nx][ny]) continue;

				q.push(make_tuple(nx,ny,nk));
				dist[nx][ny][nk] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
			}
		}

		for(int dir=0; dir<4; dir++){
			int nx = get<0>(cur) + dx[dir];
			int ny = get<1>(cur) + dy[dir];
			int nk = get<2>(cur);

			if(nx<0||nx>=h||ny<0||ny>=w) continue;
			if(dist[nx][ny][nk] || board[nx][ny]) continue;

			q.push(make_tuple(nx,ny,nk));
			dist[nx][ny][nk] = dist[get<0>(cur)][get<1>(cur)][get<2>(cur)] + 1;
		}
	}

	cout<<-1;

	return 0;
}

 

 

결과