[백준oj] 1600번 말이 되고픈 원숭이

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

---

 

풀이)

보통의 bfs문제이다. 하지만 이경우에는 말처럼 움직이는 동작까지 추가해줘야한다. 따라서 현재까지의 말처럼움직인 횟수가 k보다 작을때, 말움직임을 큐에 push해주면 된다.

 

※방문을 했는지에 대한 visited배열을 2차원이 아닌 3차원으로 설정해서 visited[i][j][k]= i,j위치에 말처럼 움직인 횟수가 k인 방법으로 도착을 해주었나 체크를 해주면 된다.

i,j에 도착했을때, 말처럼 움직인 횟수에 따라 결과가 달라질 수 있기 떄문이다.

ex)

k=1이고,

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 1 1

0 0 0 1 0

 

일때 , 말처럼 움직이는 횟수를 초반에 써버리면, (2,3)이나 (3,2)에서 말처럼 움직이지 못해서 오답이 나오니, (2,3)이나 (3,2)에서 말처럼 움직인 횟수가 0번인 경우도 체크를 해줘야 답이 나온다.

 

시간복잡도)

인접행렬 bfs이므로 O(W*H)만큼 걸리게 된다

 

코드)

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

int maze[200][200];
int n, m,k,total=0;
int mv[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
int mv2[8][2] = { {1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1} };
bool visited[200][200][32] = { 0 };
bool isIn(int i, int j) {
	return (i >= 0 && i < n&&j >= 0 && j < m);
}

void bfs() {
	queue<pair<int,pair<int,pair<int, int>>>> q;//말처럼 이동한 횟수, 총이동횟수,i,j
	q.push({ 0,{0,{0,0}} });
	visited[0][0][0] = 0;
	while (!q.empty()) {
		int nowi = q.front().second.second.first;
		int nowj = q.front().second.second.second;
		int cnt = q.front().second.first;
		int hm = q.front().first;
		q.pop();
		if (nowi == n-1 && nowj == m-1) {
			cout << cnt << "\n";
			return;
		}

		for (int ii = 0; ii < 4; ii++) {
			int ni = nowi + mv[ii][0];
			int nj = nowj + mv[ii][1];

			if (isIn(ni, nj) && maze[ni][nj] == 0 && !visited[ni][nj][hm]) {
				visited[ni][nj][hm] = true;
				q.push({ hm,{cnt + 1,{ ni,nj}} });
			}
		}
		if (hm < k) {
			for (int ii = 0; ii < 8; ii++) {
				int ni = nowi + mv2[ii][0];
				int nj = nowj + mv2[ii][1];

				if (isIn(ni, nj) && maze[ni][nj] == 0 && !visited[ni][nj][hm+1]) {
					visited[ni][nj][hm+1] = true;
					q.push({ hm+1,{cnt + 1,{ ni,nj}} });
				}
			}
		}
	}
	cout << "-1\n";
	return;
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> k;
	cin >> m >>n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maze[i][j];
		}
	}
	
	bfs();
}