[백준/BOJ] 백준 23290번 : 마법사 상어와 복제

https://www.acmicpc.net/problem/23290

23290번: 마법사 상어와 복제

 

모든 물고기를 한 칸 이동하는 함수(FishMove()), 상어가 가장 많이 물고기를 없앨 수 있도록 하는 이동 방법을 찾는 함수(SharkMoveFind(vector<int> move)), 찾은 방법으로 상어를 움직이는 함수(SharkMove()), 냄새의 수명을 줄이는 함수(SmellCheck()), 물고기를 복제하는 함수(FishCopy())로 주요 로직을 나눠 문제를 해결했다.

 

코드

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

int m, s;
int shark_dir[5][2] = { {0,0},{-1,0},{0,-1},{1,0},{0,1} };
int fish_dir[9][2] = { {0,0},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1} };
vector<pair<pair<int, int>, int>> fish_info;
vector<int> board[4][4]; //[x위치][y위치] = {각칸에 있는 물고기들의 방향 저장}
vector<int> smell[4][4]; //[x위치][y위치] = {각칸에 있는 냄새의 수명 저장}
pair<int, int> shark;

int max_cnt;
vector<int> shark_move;

void Pre()
{
	max_cnt = -1;
	shark_move.clear();
}

//모든 물고기 한칸 이동
void FishMove()
{
	for (int i = 0; i < fish_info.size(); i++)
	{
		pair<int, int> here = fish_info[i].first;
		int here_dir = fish_info[i].second;

		pair<int, int> there;
		int there_dir;

		bool move_check = false;
		for (int cnt = 0; cnt <= 7; cnt++)
		{
			there_dir = here_dir - cnt;

			if (there_dir <= 0)
				there_dir += 8;

			there = make_pair(here.first + fish_dir[there_dir][0], here.second + fish_dir[there_dir][1]);

			//해당 물고기가 here_dir 방향으로 갈 수 있는지 확인
			if (there.first < 0 || there.first >= 4 || there.second < 0 || there.second >= 4)
				continue;
			if (there.first == shark.first && there.second == shark.second)
				continue;
			if (smell[there.first][there.second].size() > 0)
				continue;

			//해당 물고기가 there_dir방향으로 움직일 수 있을때
			move_check = true;
			break;
		}

		if (move_check == true)
			board[there.first][there.second].push_back(there_dir);
		else //해당 물고기가 움직일 수 있는 곳이 없을때
			board[here.first][here.second].push_back(here_dir);
	}
}

//상어가 가장 많이 물고기를 없앨 수 있도록 이동방법을 찾기
void SharkMoveFind(vector<int> move)
{
	//3번의 이동 결정을 했을때
	if (move.size() == 3)
	{
		int cnt = 0;

		pair<int, int> here = shark;

		vector<vector<int>> board_check(4, vector<int>(4, 0));
		for (int i = 0; i < move.size(); i++)
		{
			here.first += shark_dir[move[i]][0];
			here.second += shark_dir[move[i]][1];

			//상어가 이동중에 범위를 벗어날때
			if (here.first < 0 || here.first >= 4 || here.second < 0 || here.second >= 4)
				return;

			//here위치에서 잡아먹는 물고기 개수 더하기
			if (board_check[here.first][here.second] == 0)
			{
				cnt += board[here.first][here.second].size();
				board_check[here.first][here.second] = 1; //해당 위치는 잡아 먹었다고 체크
			}

		}

		//더 많이 물고기를 없애는 방법을 찾았을때
		if (cnt > max_cnt)
		{
			max_cnt = cnt;

			shark_move.clear();
			shark_move = move;
		}

		return;
	}

	for (int i = 1; i <= 4; i++)
	{
		move.push_back(i);
		SharkMoveFind(move);
		move.pop_back();
	}

}

//찾은 방법으로 상어를 움직이기
void SharkMove()
{
	for (int i = 0; i < shark_move.size(); i++)
	{
		shark.first += shark_dir[shark_move[i]][0];
		shark.second += shark_dir[shark_move[i]][1];

		//해당 위치에 물고기가 있다면 없애고 냄새 남기기
		if (board[shark.first][shark.second].size() > 0)
		{
			board[shark.first][shark.second].clear();
			smell[shark.first][shark.second].push_back(3);
		}
	}
}

//냄새의 수명을 줄인다
void SmellCheck()
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			vector<int> new_smell;

			for (int k = 0; k < smell[i][j].size(); k++)
			{
				smell[i][j][k]--;

				//이제 없어지는 냄새일때
				if (smell[i][j][k] == 0)
					continue;

				new_smell.push_back(smell[i][j][k]);
			}

			smell[i][j].clear();
			smell[i][j] = new_smell;
		}
	}
}

void FishCopy()
{
	for (int i = 0; i < fish_info.size(); i++)
	{
		pair<int, int> here = fish_info[i].first;
		int here_dir = fish_info[i].second;

		board[here.first][here.second].push_back(here_dir);
	}

	//fish_info 새로 업데이트
	fish_info.clear();

	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			for (int k = 0; k < board[i][j].size(); k++)
			{
				fish_info.push_back(make_pair(make_pair(i, j), board[i][j][k]));
			}
			board[i][j].clear();
		}
	}
}

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

	cin >> m >> s;

	for (int i = 0; i < m; i++)
	{
		int x, y, d;
		cin >> x >> y >> d;
		x--;
		y--;

		fish_info.push_back(make_pair(make_pair(x, y), d));
	}

	int x, y;
	cin >> x >> y;
	x--;
	y--;
	shark = make_pair(x, y);

	for (int i = 0; i < s; i++)
	{
		FishMove();

		Pre();
		vector<int> move;
		SharkMoveFind(move);

		SharkMove();

		SmellCheck();

		FishCopy();
	}

	cout << fish_info.size();

	return 0;
}