골드3 - 백준 19237 어른 상어

백준 19237 어른 상어

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

접근방법

상어를 class로 선언하여 각 상어의 우선순위와 현재 위치, 방향을 저장해주고, move() 함수를 통해 움직일 수 있도록 객체를 만들어서 문제를 해결했다.

풀이

Shark 객체를 선언하였고, 각 상어의 정보를 저장해주고 move() 함수를 통해서 우선순위에 따라 움직였다. 우선 모든 우선순위를 둘러보면서 빈칸이 있는지 찾고, 없다면 한번 더 우선순위 순서로 자신의 냄새가 있는 곳으로 이동하게끔 구현하였다.
set_board() 함수는 상어가 움직이고 난 뒤에 남아있는 냄새를 -1씩 해주었고, 각 상어의 현재 위치를 확인하여 해당 위치의 냄새를 K로 설정해주었다. 이때 상어의 number가 빠른 순서로 냄새를 지정하여 주는데, 상어끼리 겹치게 될 경우 delete_stack에 상어의 인덱스를 저장하여 삭제해주었다.
매 cnt마다 남아있는 모든 상어를 움직이고 set_board()로 냄새값을 최신화 해주었고 남아있는 상어가 1마리일 때, 반복문을 탈출하여 cnt 값을 출력하였고, 1000이 넘었을 때, 탈출하여 -1을 출력하였다.

코드

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

using namespace std;

int N, M, K;
int board[20][20][2];
vector<vector<int>> dir = { {0,0}, {-1,0}, {1,0}, {0,-1}, {0,1} };

class Shark
{
public:
	int number;
	pair<int, int> location;
	int head;

	vector<vector<int>> priority;
	Shark(int number, pair<int,int> loc)
	{
		this->number = number;
		this->location = loc;
	}

	void move()
	{
		// 빈칸 먼저
		for (int i = 0; i < priority[head].size(); i++)
		{
			int cur = priority[head][i];
			int nx = location.first + dir[cur][0];
			int ny = location.second + dir[cur][1];

			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;

			if (board[nx][ny][0] != 0)
				continue;

			location.first = nx;
			location.second = ny;
			head = cur;

			return;
		}

		// 자기 냄새
		for (int i = 0; i < priority[head].size(); i++)
		{
			int cur = priority[head][i];
			int nx = location.first + dir[cur][0];
			int ny = location.second + dir[cur][1];

			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;

			if (board[nx][ny][0] != 0 && board[nx][ny][1] != number)
				continue;

			location.first = nx;
			location.second = ny;
			head = cur;

			return;
		}
	}
};

bool compare(Shark s1, Shark s2)
{
	if (s1.number < s2.number)
		return true;
	return false;
}

vector<Shark> sharks;

void set_board()
{
	// 냄새 지우기
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (board[i][j][0] == 0)
				continue;

			board[i][j][0]--;
			if (board[i][j][0] == 0)
				board[i][j][1] = 0;
		}
	}

	vector<int> delete_stack;

	// 상어 이동 결과에 따른 냄새 갱신 및 상어 삭제
	for (int i = 0; i < sharks.size(); i++)
	{
		int x = sharks[i].location.first;
		int y = sharks[i].location.second;

		if (board[x][y][1] != 0 && board[x][y][1] != sharks[i].number)
		{
			delete_stack.push_back(i);
		}
		else
		{
			board[x][y][0] = K;
			board[x][y][1] = sharks[i].number;
		}
	}

	while (!delete_stack.empty())
	{
		int index = delete_stack.back();
		delete_stack.pop_back();

		sharks.erase(sharks.begin() + index);
	}
}

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

	cin >> N >> M >> K;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> board[i][j][1];
			if (board[i][j][1] != 0)
			{
				board[i][j][0] = K;
				Shark s = Shark(board[i][j][1], { i,j });
				sharks.push_back(s);
			}
		}
	}

	sort(sharks.begin(), sharks.end(), compare);

	for (int i = 0; i < M; i++)
		cin >> sharks[i].head;

	for (int i = 0; i < M; i++)
	{
		vector<vector<int>> temp;
		vector<int> xxx;
		temp.push_back(xxx);

		for (int j = 0; j < 4; j++)
		{
			vector<int> t;
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			t.push_back(a);
			t.push_back(b);
			t.push_back(c);
			t.push_back(d);
			temp.push_back(t);
		}

		sharks[i].priority = temp;
	}

	int cnt = 0;
	bool flag = false;

	while (cnt < 1000)
	{
		cnt++;
		for (int i = 0; i < sharks.size(); i++)
			sharks[i].move();
		set_board();

		if (sharks.size() == 1)
		{
			flag = true;
			break;
		}
	}

	if (flag)
		cout << cnt << endl;
	else
		cout << -1 << endl;

	return 0;
}