백준 19236번 _ 청소년 상어

www.acmicpc.net/problem/19236

19236번: 청소년 상어

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Fish
{
public:
	bool isAlive = true;
	short y;
	short x;
	short dir;
	Fish() {}
	Fish(int y_in, int x_in, int dir_in) :y(y_in), x(x_in), dir(dir_in) {}
};

int board[4][4];
vector<Fish> fishes(17);
int dy[9] = { 0, -1, -1, 0, 1, 1, 1, 0, -1 };
int dx[9] = { 0, 0, -1, -1, -1, 0, 1, 1, 1 };

bool IsInRange(int y, int x)
{
	if (y >= 0 && y < 4 && x >= 0 && x < 4)
		return true;
	return false;
}

void boardInit()
{
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			board[i][j] = -1;
}

//y,x는 상어 좌표
int answer = 0;
void dfs(vector<Fish>fishData, int sum)
{
	Fish shark = move(fishData[0]);

	//범위 안에 드는지 확인, 범위 밖으로 나갔으면 집간거임 값갱신
	if (IsInRange(shark.y, shark.x) == false)
	{
		answer = max(answer, sum);
		return;
	}

	//보드 갱신
	boardInit();
	for (int i = 1; i < fishData.size(); i++)
	{
		Fish fish = fishData[i];
		if (fish.isAlive == false)
			continue;
		board[fish.y][fish.x] = i;
	}

	//상어 움직임 갱신
	int eatFishNumber = board[shark.y][shark.x];
	if (eatFishNumber == -1)
	{
		answer = max(answer, sum);
		return;
	}
	sum += eatFishNumber;
	shark.dir = fishData[eatFishNumber].dir;
	fishData[eatFishNumber].isAlive = false;
	board[shark.y][shark.x] = 0;

	//물고기 움직이기
	for (int i = 1; i <= 16; i++)
	{
		Fish& fish = fishData[i];
		if (fish.isAlive == false)
			continue;

		int ny, nx, fdir = fish.dir;

		//방향이 바뀔수 있으므로 8번도는 for문
		for (int j = 0; j < 8; j++)
		{
			ny = fish.y + dy[fdir];
			nx = fish.x + dx[fdir];

			//범위를 넘을경우, 상어가 있을 경우
			if (IsInRange(ny, nx) == false || board[ny][nx] == 0)
			{
				if (fdir >= 8)
					fdir = 1;
				else
					fdir++;
				continue;
			}

			int changeFishNum = board[ny][nx];
			fish.dir = fdir;

			//물고기가 있을때 서로 바꿔줘야함
			if (changeFishNum != -1)
			{
				board[fish.y][fish.x] = changeFishNum;
				board[ny][nx] = i;
				fishData[changeFishNum].y = fish.y;
				fishData[changeFishNum].x = fish.x;
				fish.y = ny;
				fish.x = nx;
			}
			//빈공간일 경우
			else
			{
				board[fish.y][fish.x] = -1;
				board[ny][nx] = i;
				fish.y = ny;
				fish.x = nx;
			}
			break;
		}
	}

	//다음상어 움직임. 
	for (int i = 1; i <= 4; i++)
	{
		int ny = shark.y + (dy[shark.dir] * i);
		int nx = shark.x + (dx[shark.dir] * i);
		Fish nShark = shark;
		nShark.y = ny;
		nShark.x = nx;
		fishData[0] = nShark;
		dfs(fishData, sum);
	}
}

int main()
{
	//Input
	Fish shark(0, 0, 0);
	fishes[0] = shark;
	int idx, dir;
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			cin >> idx >> dir;
			Fish fish(i, j, dir);
			fishes[idx] = fish;
		}
	}

	//simulation
	dfs(fishes, 0);
	cout << answer << '\n';

	return 0;
}