[BOJ] 19236 - 청소년상어

[백준] 19236 - 청소년상어

재귀를 반복하면서 계속해서 새로운 배열을 생성해야 하기 때문에 메모리 초과가 날 수도 있다고 생각해 걱정했던 코드다.
다행히 재귀 깊이가 최대 16이기 때문에 우려하던 문제는 발생하지 않았다.
주어진 대로 충실히 구현하고, 최댓값은 가능한 모든 경우의 수를 DFS방식으로 탐색하고 반환된 값 중에 최댓값을 선택하여 반환하여 구해주었다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;
typedef pair<int, int> PII;

const int dr[8] = { -1, -1, 0, 1, 1, 1, 0, -1 }, dc[8] = { 0, -1, -1, -1, 0, 1, 1, 1 };
int k;
vector<vector<int>> fild;
vector<PII> mouse;
vector<int> to;

bool is_in_range(int x, int y) {
	return x >= 0 && x < 4 && y >= 0 && y < 4;
}

void mouse_move(vector<vector<int>> &fild, vector<PII> &mouse, vector<int> &to, int x, int y) {
	for (int i = 1; i <= 16; i++) {
		if (mouse[i].first == -1) continue;
		int xx = mouse[i].first, yy = mouse[i].second;
		while (true) {
			int r = xx + dr[to[i]], c = yy + dc[to[i]];
			if (is_in_range(r, c) && (r != x || c != y)) { // 이동이 가능한 경우
				if (fild[r][c] != 0) {
					swap(mouse[i], mouse[fild[r][c]]);
					swap(fild[r][c], fild[xx][yy]);
				}
				else {
					fild[r][c] = fild[xx][yy];
					fild[xx][yy] = 0;
					mouse[i] = { r,c };
				}
				break;
			}
			else {
				to[i]++;
				if (to[i] >= 8) to[i] -= 8;
			}

		}
	}
}

int go(vector<vector<int>> fild, vector<PII> mouse, vector<int> to, int x, int y) {
	int rtn = fild[x][y], now = fild[x][y];
	fild[x][y] = 0;
	mouse[now] = { -1, -1 };
	mouse_move(fild, mouse, to, x, y);
	for (int i = 1; i < 4; i++) {
		int r = x + i * dr[to[now]], c = y + i * dc[to[now]];
		if (is_in_range(r, c) && fild[r][c] != 0) {
			rtn = max(rtn, now + go(fild, mouse, to, r, c));
		}
	}
	return rtn;
}

int main(void) {
	to.resize(20);
	mouse.resize(20);
	fild.resize(4);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			int a, b;
			scanf("%d %d", &a, &b);
			fild[i].push_back(a);
			mouse[a] = { i, j };
			to[a] = b - 1;
		}
	}
	printf("%d", go(fild, mouse, to, 0, 0));
	return 0;
}