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

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

아이디어는 어렵지 않은데 코드로 구현해내는 방식이 어려웠다.

cur.first.first 와 cur.first.second 에 각각 원숭이의 x, y좌표를

cur.second.first 와 cur.second.second에 각각 말처럼 이동한 횟수, 총이동 횟수를 저장하였다.

BFS과정을 통해 진행되며 도착점(오른쪽 하단)에 최초로 도착하게 될 때, cur.second.second + 1의 값을 출력한다.

(BFS특성상 cur.second.second의 값이 연속되게 큐에 들어가기 때문에 최초이후의 값은 최초보다 무조건 크거나 같다.)

//1600
#include <iostream>
#include <queue>
#include <deque>

using namespace std;

int board[200][200];
int vis[200][200][31];
int W, H, K;
int dx[12] = { 0, 0, -1, 1, 1, 1, 2, 2, -1, -1, -2, -2 };
int dy[12] = { -1, 1, 0, 0, 2, -2, 1, -1, 2, -2, 1, -1 };
queue<pair<pair<int, int>, pair<int, int>>> q;

void BFS() {

	q.push({ {0, 0}, {0, 0} });
	vis[0][0][1] = 1;
	while (!q.empty()) {
		pair<pair<int, int>, pair<int, int>> cur;
		cur = q.front();
		q.pop();

		for (int dir = 0; dir < 12; dir++) {

			if (dir >= 4 && cur.second.first >= K)
				continue;

			int nx = cur.first.first + dx[dir];
			int ny = cur.first.second + dy[dir];
			int nz = cur.second.first;

			if (dir >= 4)
				nz += 1;

			if (nx < 0 || ny < 0 || nx >= H || ny >= W)
				continue;

			if (nx == H - 1 && ny == W - 1) {
				cout << cur.second.second + 1;
				return;
			}

			if (board[nx][ny] == 1 || (nx == 0 && ny == 0))
				continue;
			if (vis[nx][ny][nz] == 0) {

				vis[nx][ny][nz] = vis[cur.first.first][cur.first.second][cur.second.first] + 1;
				if (dir < 4) {
					q.push({ { nx, ny}, {cur.second.first, cur.second.second + 1} });
				}
				else {
					q.push({ { nx, ny}, {cur.second.first + 1, cur.second.second + 1} });
				}

			}
		}
	}
	cout << -1;
}

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

	cin >> K >> W >> H;

	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			cin >> board[i][j];

	if (H == 1 && W == 1) {
		cout << 0;
		return 0;
	}		

	BFS();
}