[백준/BOJ] 백준 19236번 : 청소년 상어

www.acmicpc.net/problem/19236

19236번: 청소년 상어

상어가 움직이는 함수와 물고기가 움직이는 함수에 매개변수로 (shark shark_info, vector<fish> fish_info, vector<vector<int>> board, int sum)를 해서, 그 상황의 상어 정보, 물고기들의 정보, 보드 상황, 상어가 먹은 물고기 번호의 합을 전달하며 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct shark {
	int x;
	int y;
	int dir;
};

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

void Shark_Move(shark shark_info, vector<fish> fish_info, vector<vector<int>> board, int sum);
void fish_Move(shark shark_info, vector<fish> fish_info, vector<vector<int>> board, int sum);

int dxdy[9][2] = { {0,0}, {-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,1} };
int result = -987654321;

//상어 움직임
void Shark_Move(shark shark_info, vector<fish> fish_info, vector<vector<int>> board, int sum)
{
	int here_x = shark_info.x;
	int here_y = shark_info.y;
	int here_dir = shark_info.dir;
	int can = false;

	for (int i = 1; i <= 4; i++)
	{
		int there_x = here_x + (dxdy[here_dir][0] * i);
		int there_y = here_y + (dxdy[here_dir][1] * i);
		int there_dir = here_dir;

		//범위를 넘어갔을때
		if (there_x < 0 || there_x >= 4 || there_y < 0 || there_y >= 4)
			break;

		//빈칸일때
		if (board[there_x][there_y] == 0)
			continue;

		can = true;

		shark new_shark_info;
		vector<fish> new_fish_info(fish_info);
		vector<vector<int>> new_board(board);
		int new_sum;

		int there_fish = board[there_x][there_y];

		new_shark_info = { there_x, there_y, fish_info[there_fish].dir };
		new_fish_info[there_fish] = { -1,-1,-1 };
		new_board[here_x][here_y] = 0;
		new_board[there_x][there_y] = -1;
		new_sum = sum + there_fish;

		fish_Move(new_shark_info, new_fish_info, new_board, new_sum);
	}

	if (can == false) //더이상 갈 수 있는곳이 없을때
	{
		result = max(result, sum);
		return;
	}
}

//물고기들 움직임
void fish_Move(shark shark_info, vector<fish> fish_info, vector<vector<int>> board, int sum)
{
	//1번부터 16번물고기 까지 움직임
	for (int i = 1; i <= 16; i++)
	{
		//이미 없어진 물고기 일때
		if (fish_info[i].dir == -1)
			continue;

		int here_x = fish_info[i].x;
		int here_y = fish_info[i].y;
		int here_dir = fish_info[i].dir;
		bool there_find = false;

		for (int j = 0; j < 8; j++)
		{
			int there_dir = here_dir + j;

			if (there_dir > 8) //방향의 범위는 1~8
				there_dir -= 8;

			int there_x = here_x + dxdy[there_dir][0];
			int there_y = here_y + dxdy[there_dir][1];

			//범위를 벗어날때
			if (there_x < 0 || there_x >= 4 || there_y < 0 || there_y >= 4)
				continue;

			if (board[there_x][there_y] != -1) //there위치에 상어가 없을때 (움직일 수 있을때)
			{
				there_find = true;

				if (board[there_x][there_y] == 0) //there가 빈칸일때 (빈칸으로 이동)
				{
					//i물고기의 정보 업데이트
					fish_info[i].x = there_x;
					fish_info[i].y = there_y;
					fish_info[i].dir = there_dir;

					//board판 업데이트
					board[here_x][here_y] = 0;
					board[there_x][there_y] = i;
				}

				else //there가 물고기 위치일때
				{
					//there 자리에 원래 있던 물고기
					int there_fish = board[there_x][there_y];

					//i물고기의 정보 업데이트
					fish_info[i].x = there_x;
					fish_info[i].y = there_y;
					fish_info[i].dir = there_dir;

					//원래 있던 자리 물고기 정보 업데이트
					fish_info[there_fish].x = here_x;
					fish_info[there_fish].y = here_y;

					//board판 업데이트
					board[here_x][here_y] = there_fish;
					board[there_x][there_y] = i;
				}

				break;
			}

		}

	}

	Shark_Move(shark_info, fish_info, board, sum);
}

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

	shark shark_info; //상어의 위치와 방향
	vector<fish> fish_info(17); //물고기들의 정보
	vector<vector<int>> board(16, vector<int>(16, 0)); //board판 상황

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
		{
			int a, b;

			cin >> a >> b;

			fish_info[a] = { i,j,b };
			board[i][j] = a;
		}

	int first_delete_fish = board[0][0];

	shark_info = { 0,0,fish_info[first_delete_fish].dir }; //초기 상어의 정보
	fish_info[first_delete_fish] = { -1,-1,-1 }; //없이진 물고기는 모두 -1로 표시
	board[0][0] = -1; //상어의 위치는 board에서 -1로 표시
	int sum = first_delete_fish;

	fish_Move(shark_info, fish_info, board, sum); //물고기 움직임

	cout << result;

	return 0;
}