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

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

코드

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

#define MAX 201
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);

typedef pair<int, int> pi;
int arr[MAX][MAX], w, h, k, ans = INT_MAX;
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
int ddx[8] = { -2, -1, -2, -1, 1, 2, 1, 2 };
int ddy[8] = { 1, 2, -1, -2, 2, 1, -2, -1 };
bool visit[MAX][MAX][31];

void bfs() {
	queue<pair<pi, pi>> q;

	q.push({ { 0, 0 }, {0 , 0} });
	visit[0][0][0] = true;

	while (!q.empty()) {
		int nx = q.front().first.first;
		int ny = q.front().first.second;

		int cnt = q.front().second.first;
		int use = q.front().second.second;

		q.pop();

		if (nx == h - 1 && ny == w - 1) {
			ans = min(ans, cnt);
			continue;
		}

		for (int i = 0; i < 4; i++) {
			int gx = nx + dx[i];
			int gy = ny + dy[i];

			if (gx >= 0 && gx < h && gy >= 0 && gy < w && !visit[gx][gy][use] && !arr[gx][gy]) {
				q.push({ { gx, gy }, { cnt + 1, use } });
				visit[gx][gy][use] = true;
			}
		}

		if (use >= k) continue;
		for (int i = 0; i < 8; i++) {
			int gx = nx + ddx[i];
			int gy = ny + ddy[i];

			if (gx >= 0 && gx < h && gy >= 0 && gy < w && !visit[gx][gy][use+1] && !arr[gx][gy]) {
				q.push({ { gx, gy }, { cnt + 1, use+1 } });
				visit[gx][gy][use+1] = true;
			}
		}
	}
}

int main() {
	FASTIO;
	cin >> k >> w >> h;

	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> arr[i][j];


	bfs();
	if (ans == INT_MAX) cout << -1;
	else cout << ans;
	return 0;
}

 

설명

BFS 구현 문제입니다. 3차원 배열로 위치뿐만 아니라 말의 움직임으로 이동한 것까지 방문 처리하면서 풀면 됩니다.
 
격자판 정보를 받고 BFS를 돌려줍니다. 저는 격자판 좌표, 현재 움직임 횟수, 말의 움직임으로 이동한 횟수를 큐에 넣어서 관리해주었습니다. 단순 상하좌우 이동은 횟수 제한이 없지만, 말의 움직임으로 이동하는 것은 횟수 제한이 있으므로 말처럼 이동하기 전에 지금 상황에 오기까지 말처럼 이동한 횟수를 확인해줍니다. 도착지점에 오면 매번 ans를 최솟값으로 갱신해주고 bfs 함수가 종료되면 ans를 출력하고 전체 프로그램을 종료합니다.
 
 

느낀 점

어려운 문제는 아닌데, 구현에서 두 번 정도 실수를 했습니다... 첫 번째는 가로 세로를 반대로 받았던 거였는데 예제 2번에서 바로 찾아서 고쳤습니다.  근데 두 번째 실수를 찾기 어려웠습니다.

정답

오답

말의 이동 방향을 실수해서 계속 46% 쯤에서 틀렸던 거였습니다. 저는 제 코드 로직이 문제인 줄 알고 계속 게시판에서 테스트케이스를 돌려보는데, 다 통과했었어서 아예 다시 짤까 고민도 했었습니다... 
 
그래도 나름 금방 찾아서 다행입니다.