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

문제 

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

1600번: 말이 되고픈 원숭이

 

풀이 

[BFS + 구조체]

BFS를 이용해서 풀면 되는 문제였다.

일반적인 BFS에서, 상하좌우로 이동하는 것만을 고려했다면, 

이 문제에서는 "말 처럼 이동할 수 있는 경우"도 고려해서 BFS를 돌려주면 되는 문제였다.

다만 "말 처럼 움직일 수 있는 횟수"가 K번으로 정해져있으므로, 남은 횟수 k도 큐에 넣어 확인해주었다. 

 

* 처음에 visited배열을 2차원으로 만들어서 위치만 체크했었는데, k도 이용해서 visited를 체크해주어야 한다! 

https://www.acmicpc.net/board/view/40044 (이런 문제를 발견하게된 반례)

 

* W와 H가 모두 1인 경우도 고려해주어야 한다 

https://www.acmicpc.net/board/view/67499 

 

코드 

#include <iostream>
#include <queue>

using namespace std;

int K, W, H;
bool table[200][200];
bool visited[31][200][200] = { 0, }; //k가 몇번 남았는지에 따라 visited를 다르게 해줘야함 

int dh[4] = { -1,1,0,0 }; // 상하좌우 
int dw[4] = { 0,0,-1,1 };

int horseH[8] = { -2,-2,-1,1,2, 2, 1,-1 };
int horseW[8] = { -1, 1, 2,2,1,-1,-2,-2 };

struct Node { 
	int h;
	int w;
	int k; //말 처럼 이동할 수 있는 남은 횟수
	int count; //지금까지 움직인 횟수 
};
int BFS(int startH, int startW) {
	queue<Node> q;
	q.push({ startH, startW, K, 0 });
	visited[K][startH][startW] = 1;

	while (!q.empty()) {
		int tempH = q.front().h;
		int tempW = q.front().w;
		int k = q.front().k;
		int count = q.front().count;

		q.pop();

		int nextH, nextW;
		if (k > 0) { // 말처럼 이동
			for (int i = 0;i < 8;i++) {
				nextH = tempH + horseH[i];
				nextW = tempW + horseW[i];
				if (nextH < 0 || nextH >= H || nextW < 0 || nextW >= W) continue; //table 범위 안인지 체크
				if (!visited[k-1][nextH][nextW] && !table[nextH][nextW]) { // 방문한적이 없고, 평지이면 이동 
					if (nextH == H - 1 && nextW == W - 1) return count + 1; // 도착지이면 return  
					visited[k - 1][nextH][nextW] = 1;
					q.push({ nextH, nextW, k - 1, count + 1 });
				}
			}
		}
		for (int i = 0;i < 4;i++) { // 상하좌우 이동 
			nextH = tempH + dh[i];
			nextW = tempW + dw[i];
			if (nextH < 0 || nextH >= H || nextW < 0 || nextW >= W) continue; //table 범위 안인지 체크
			if (!visited[k][nextH][nextW] && !table[nextH][nextW]) { // 방문한적이 없고, 평지이면 이동 
				if (nextH == H - 1 && nextW == W - 1) return count + 1; // 도착지이면 return  
				visited[k][nextH][nextW] = 1;
				q.push({ nextH, nextW, k, count + 1 });
			}
		}
	}
	return -1;
}
int main() {
	cin >> K >> W >> H;
	for (int h = 0;h < H;h++) {
		for (int w = 0;w < W;w++) {
			cin >> table[h][w];
		}
	}
	
	// H와 W가 모두 1이 될 수 있음! (문제를 꼼꼼히 읽자) 
	if (H == 1 && W == 1) {
		cout << 0 << endl;
		return 0;
	}
	int result = BFS(0, 0);
	cout << result << endl;
	return 0;
}

 

결과