어른상어 [백준:19237]골드

 

 

 

으른 상어

 

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

 

 

 

문제의 구조는

입력받기

 

상어의 이동 방향  데이터 받아오기

상어의 이동

상어의 냄새 남기기

 

순서로 진행한다.

 

 

위이미지처럼 1번 상어부터 

오른쪽을 보기에  맨 아래  오른쪽 왼쪽 위아래 순으로 탐색한다.

 

냄새를 남긴다.

 

만약 겹칠 경우 낮은 값을 가진 상어가 이긴다.

 

 

해당 문제를 해결할 때 냄새를 업데이트한다면 시간이 많이 걸릴 것이라 생각했기에 time으로 그냥 계산해 준다.

 

 

 

 

해당 문제에서 26 퍼에서 틀린다면 1000 이상 인지 초과인지  개발 순서의 시간을 언제 업데이트

하는지 확인해야 한다. 

 

 

 

 

#include<iostream>
#include<vector>

using namespace std;
static const int SharkBasic_Mover[4][2] = { {0,-1} ,{0,1}, {-1,0}, {1,0} };
enum direction {
	UP = 0,
	DOWN,
	LEFT,
	RIGHT
};
struct Shark
{
public:
	Shark() {
		Mover = vector<vector<direction>>(4, vector<direction>(4));
		Sharknumber = -1;
		PosX = -1, PosY = -1;
	}

	vector<vector<direction>> Mover;
	direction dir;
	int PosX, PosY, Sharknumber;
	bool IS_Alive = true;
};

void AdultShark() {
	//N*N , M개상어, K냄새 남는시간
	int N = 0, M = 0, K = 0, time = 0;
	//현재시간과 비교해서 사라졌는지 확인
	cin >> N >> M >> K;
	vector< Shark>Sharks(M, Shark());
	vector<vector<pair<int, int>>> World(N, vector<pair<int, int>>(N, make_pair(-1, -1)));
	int num = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> num;
			if (num != 0) {
				Sharks[num - 1].PosX = j;
				Sharks[num - 1].PosY = i;
				Sharks[num - 1].Sharknumber = num - 1;
				World[j][i] = make_pair(num - 1, time);

			}
		}
	}
	//상어방향
	for (int i = 0; i < M; ++i) {
		cin >> num;
		Sharks[i].dir = direction(num - 1);
	}
	//방향우선순위
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < 4; ++j) {
			for (int k = 0; k < 4; ++k) {
				cin >> num;
				Sharks[i].Mover[j][k] = direction(num - 1);
			}
		}
	}
	vector<direction>* MoveDir;
	int x = 0, y = 0;
	while (M != 1)
	{
		time++;
		//이동할 위치 넣기
		for (Shark& S : Sharks) {
			if (S.IS_Alive == false) continue;
			//move
			MoveDir = &(S.Mover[S.dir]);
			direction nowdir = S.dir;
			int Smellx = -1, Smelly = -1;
			bool ISMove = false;
			for (int i = 0; i < MoveDir->size(); ++i) {

				x = S.PosX + SharkBasic_Mover[(int)((*MoveDir)[i])][0];
				y = S.PosY + SharkBasic_Mover[(int)((*MoveDir)[i])][1];
				if (x < 0 || N <= x || y < 0 || N <= y)continue;
				if (World[x][y].first == -1) {
					S.dir = (*MoveDir)[i];
					S.PosX = x;
					S.PosY = y;
					ISMove = true;
					break;
				}
				else {
					// 현재 -   기록 시간       유지시간
					if (((time - World[x][y].second) > K)) { //  (3time - 1) 2냄새 지남 
						//빈칸취급
						S.dir = (*MoveDir)[i];
						S.PosX = x;
						S.PosY = y;
						ISMove = true;
						break;
					}//                                              선턴
					else if (World[x][y].first == S.Sharknumber && Smellx == -1) {
						Smellx = x;
						Smelly = y;
						nowdir = (*MoveDir)[i];
					}
				}
			}
			//냄새칸 첫위치
			if (ISMove == false) {
				S.PosX = Smellx;
				S.PosY = Smelly;
				S.dir = nowdir;
			}
		}


		for (int i = 0 ; i < Sharks.size();++i)
		{
			Shark& S = Sharks[i];
			if (S.IS_Alive == false) continue;

			if (World[S.PosX][S.PosY].second == time) {
				S.IS_Alive = false;
				M--;
			}
			else
			{
				World[S.PosX][S.PosY] = make_pair(S.Sharknumber, time);
			}
		}

		if (time > 1000) { time = -1; break; }
	}
	cout << time;
}

int main() {


	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	AdultShark();
}