19236번 청소년 상어

얻을게 많은 문제이다.
시뮬레이션과 구현파트에 있는 문제인데, 결국에는 재귀(DFS)나 BFS를 사용한다.
이번 문제는 재귀를 사용한다.
1. 문제를 풀때마다 들었던 의문이 있다. 이 문제는 브루트포스인가? 그리디인가? 아직까지 내가 만난 문제들은 명확한 답을 요구하기 때문에(모든 문제가 그럴것 같다.) 어지간하면 브루트포스를 사용해야 한다. 이 문제 역시 그러한데, 브루트포스 중, 재귀를 통해 최대값을 뽑아낸다.
2. 또 하나 얻어갈 것이 있다면, 이번 문제는 배열판이 계속해서 변한다. 따라서 이것들을 동적으로 움직이려면 함수안에 벡터를 넣어주는것이 편하다.
3. 브루트포스의 기본 개념은 "일일이 대입해봐라"가 기본 모토이기 때문에 3중 for문 정도는 거뜬하게 사용한다. 앞으로 확신이 들면 바로바로 사용하자.
4. 재귀가 좋은 것이 있다면, 한번 재귀를 통해 값이 전해지면 그 이후에는 신경쓰지 않아도 된다. 다시 check배열을 0->1->0으로 해줄 필요가 없다는 말이다. BFS는 해줘야하는 경우가 종종 있다. 이 문제에서도 상어의 위치가 정말 최적의 위치인가? 다른 곳으로 가는 것이 최적인데, 이미 잘못 떠난 경우는 어떡하징? 이럴 필요가 없다는 것이다. 굿~
5. 재귀를 사용할 때 반환형이 있는게 나은지, void인게 나은지 아직도 조금 고민이 된다. 이번 문제같은 경우에는 "너가 최적인지 한번 다녀와바라~"하는 느낌이어서 되돌아오는 값이 있는게(주로 int형) 좋은 것 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dx[] = { -1,-1, 0, 1,1,1,0,-1 };
int dy[] = {  0,-1,-1,-1,0,1,1, 1 };
int DFS(vector<vector<int>> number, vector<vector<int>> dir,int x, int y, int direction) {
	//물고기 이동
	for (int a = 1; a <= 16;a++) {
		bool f = false;
		for (int i = 0; i < 4; i++) {
			//cout << "error5" <<" "<<i<<" " <<'\n';
			for (int j = 0; j < 4; j++) {
				if (number[i][j] == a) {
					for (int k = 0; k < 8; k++) {
						int xx = i + dx[dir[i][j]];
						int yy = j + dy[dir[i][j]];
						if (xx >= 0 && xx < 4 && yy < 4 && yy >= 0&&number[xx][yy] >= 0 && !(xx == x && yy == y) ) {
							//cout << "error4" << '\n';
							swap(number[i][j], number[xx][yy]);
							swap(dir[i][j], dir[xx][yy]);
							f = true;
							break;
						}
						else {
							dir[i][j] += 1;
							dir[i][j] %= 8;
						}
					}
				}
				if (f) break;
			}
			if (f) break;
		}
		
	}
	//cout << "error3" <<'\n';


	//상어가 먹이찾으러 출동~
	int ans = 0;
	int xx = x + dx[direction];
	int yy = y + dy[direction];
	while (xx < 4 && xx >= 0 && yy < 4 && yy >= 0) {
		//cout << "error" << xx << yy << '\n';
		if (number[xx][yy] != 0) {
			int save = number[xx][yy];
			number[xx][yy] = 0;
			int cur = save + DFS(number, dir, xx, yy, dir[xx][yy]);
			if(ans<cur) ans = cur;
			number[xx][yy] = save;
			
		}
		xx += dx[direction];
		yy += dy[direction];
	}
	return ans;
	

}


int main() {
	//freopen("in1.txt", "rt", stdin);
	vector<vector<int>> number(4, vector<int>(4));
	vector<vector<int>> dir(4,vector<int>(4));
	//int cnt = 1;
	int n, d;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> n >> d;
			number[i][j] = n;
			dir[i][j] = d;
			dir[i][j] -= 1; 
		}
	}
	
	//cout << "error"  << '\n';
	int res = number[0][0];
	number[0][0] = 0;
	//cout << "error2" << '\n';
	res += DFS(number, dir, 0, 0, dir[0][0]);
	cout << res << '\n';

	return 0;
}