[BOJ] 백준 19236번 : 청소년 상어 C++ : 아주정은

이문제를 푸는데 정말 오랜시간이 걸린것같다. 혼자서 풀다가 힘들어서 다른사람의 블로그를 뒤져봤다.

 

정말 오랜만에 푸는거라 코드도 노가다가 정말 많았다.

 

이문제는 물고기의 이동이 첫번째 난관이고 상어가 먹는것을 DFS형태로 완전탐색을 해주면 된다.

트리구조로 이루어진다. 전역변수를 max_eat을 두고 큰값이 나오면 갱신해 주는 형태로 했다. 코드가 굉장히 비효율적으로 짜졌지만 직관적이라 이해하는데 도움은 될것같다. 다음에 다시 리팩토링해서 올리면 좋을것같다......

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct fish {
	int x;
	int dir;
};
struct pos {
	int x;
	int y;
};

int max_eat = 0;

int xdir[9] = {0,-1,-1,0,1,1,1,0,-1};
int ydir[9] = {0,0,-1,-1,-1,0,1,1,1};

void dfs(fish board[4][4], int eat_num, int ox, int oy, int nx, int ny) {
	eat_num += board[nx][ny].x;
	board[nx][ny].x = 17;
	if (ox != -1 and oy != -1) {
		board[ox][oy].x = 0;
		board[ox][oy].dir = 0;
	}
	fish temp;
	for (int k = 1; k <= 16; k++) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				if (board[i][j].x == k) {
					//fish move
					while (1) {
						if (i + xdir[board[i][j].dir] < 0 or i + xdir[board[i][j].dir] >= 4 or j + ydir[board[i][j].dir] < 0 or j + ydir[board[i][j].dir] >= 4) {
							board[i][j].dir = board[i][j].dir+1;
							if (board[i][j].dir == 9)board[i][j].dir = 1;
							continue;
						}
						else if (board[i + xdir[board[i][j].dir]][j + ydir[board[i][j].dir]].x == 17) {
							board[i][j].dir = board[i][j].dir + 1;
							if (board[i][j].dir == 9)board[i][j].dir = 1;

							continue;
						}
						else {
							temp = board[i + xdir[board[i][j].dir]][j + ydir[board[i][j].dir]];
							board[i + xdir[board[i][j].dir]][j + ydir[board[i][j].dir]] = board[i][j];
							board[i][j] = temp;
							goto silver;
						}
					}
				}
			}
		}
	silver:;
	}

	//먹을거 결정
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (board[i][j].x == 17) {
				if (board[i][j].dir == 1) {
					vector<pos> vec;
					if (i - 1 < 0) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i - 1;
					while (1) {
						if (board[t_i][j].x != 0)vec.push_back({ t_i,j });
						t_i--;
						if (t_i < 0)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}

				}
				else if (board[i][j].dir == 2) {
					vector<pos> vec;
					if (i - 1 < 0 or j - 1 < 0) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i - 1, t_j = j - 1;
					while (1) {
						if (board[t_i][t_j].x != 0)vec.push_back({ t_i,t_j });
						t_i--;
						t_j--;
						if (t_i < 0 or t_j < 0)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 3) {
					vector<pos> vec;
					if (j - 1 < 0) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_j = j - 1;
					while (1) {
						if (board[i][t_j].x != 0)vec.push_back({ i,t_j });
						t_j--;
						if (t_j < 0)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 4) {
					vector<pos> vec;
					if (i + 1 >= 4 or j - 1 < 0) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i + 1, t_j = j - 1;
					while (1) {
						if (board[t_i][t_j].x != 0)vec.push_back({ t_i,t_j });
						t_i++;
						t_j--;
						if (t_i >= 4 or t_j < 0)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 5) {
					vector<pos> vec;
					if (i + 1 >= 4) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i + 1;
					while (1) {
						if (board[t_i][j].x != 0)vec.push_back({ t_i, j });
						t_i++;
						if (t_i >= 4)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 6) {
					vector<pos> vec;
					if (i + 1 >= 4 or j + 1 >= 4) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i + 1, t_j = j + 1;
					while (1) {
						if (board[t_i][t_j].x != 0)vec.push_back({ t_i,t_j });
						t_i++;
						t_j++;
						if (t_i >= 4 or t_j >= 4)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 7) {
					vector<pos> vec;
					if (j + 1 >= 4) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_j = j + 1;
					while (1) {
						if (board[i][t_j].x != 0)vec.push_back({ i,t_j });
						t_j++;
						if (t_j >= 4)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
				else if (board[i][j].dir == 8) {
					vector<pos> vec;
					if (i - 1 < 0 or j + 1 >= 4) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					int t_i = i - 1, t_j = j + 1;
					while (1) {
						if (board[t_i][t_j].x != 0)vec.push_back({ t_i,t_j });
						t_i--;
						t_j++;
						if (t_i < 0 or t_j >= 4)break;
					}
					if (vec.empty()) {
						if (max_eat < eat_num)max_eat = eat_num;
						return;
					}
					while (!vec.empty()) {
						pos cur = vec.back();
						vec.pop_back();
						fish temp_board[4][4];
						for (int k = 0; k < 4; k++) {
							for (int t = 0; t < 4; t++) {
								temp_board[k][t] = board[k][t];
							}
						}
						dfs(temp_board, eat_num, i, j, cur.x, cur.y);
					}
				}
			}
		}
	}
}

int main() {
	fish arr[4][4];
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> arr[i][j].x >> arr[i][j].dir;
		}
	}//입력받기
	dfs(arr, 0, -1, -1, 0, 0);
	cout << max_eat << endl;
}