백준 19237번 _ 어른 상어

www.acmicpc.net/problem/19237

19237번: 어른 상어

---

풀이방법

1. 먼저 상어를 클래스로 정의해두었다.

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

2. 방향의 우선순위와 냄새에 관한 배열, 상어의 현황을 표시해주는 맵등을 정의해주었다.

//idx, time순
pair<int, int> smell[20][20];
int map[20][20];
int M, N, K;
vector<vector<vector<int>>>dir;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
vector<Shark> sharks;

3. 입력을 받는다.

void Input()
{
	//map 입력
	cin >> N >> M >> K;
	sharks.resize(M);
	dir.resize(M);
	for (int i = 0; i < M; i++)
		dir[i].resize(4);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int mapVal;
			cin >> mapVal;

			if (mapVal == 0)
				continue;
			
			Shark shark(i, j);
			sharks[mapVal - 1] = shark;
		}
	}

	//방향 입력
	for (int i = 0; i < M; i++)
	{
		int shDir;
		cin >> shDir;
		sharks[i].dir = shDir - 1;
	}

	//우선순위 입력
	for (int idx = 0; idx < M; idx++)
	{
		//방향 상 하 좌 우
		for (int d = 0; d < 4; d++)
		{
			dir[idx][d].resize(4);
			for (int i = 0; i < 4; i++)
			{
				cin >> dir[idx][d][i];
			}
		}
	}
}

4. 시뮬레이션을 푼다.

void simulation()
{
	int answer = -1;
	int t = 0;
	smellInit();
	remainSmell(t);
	for (t = 1; t <= 1000; t++)
	{
		//상어 움직이기
		MoveSharks(t);

		//겹친 상어가 있는지 확인
		//맵 갱신
		mapInit();
		for (int i = 0; i < sharks.size(); i++)
		{
			Shark& shark = sharks[i];
			if (shark.isAlive == false)
				continue;
			//겹쳤는데  잡아먹힘
			if (map[shark.y][shark.x] < i && map[shark.y][shark.x] != -1 )
			{
				shark.isAlive = false;
			}
			//그자리에 배치
			else
			{
				map[shark.y][shark.x] = i;
			}
		}

		//냄새 남기기
		remainSmell(t);

		//1번 상어만 남았는지 확인
		if (IsEndSituation() == true)
		{
			answer = t;
			break;
		}
	}
	cout << answer << endl;
}

 

조금더 편하게 푸는 방법으로는 냄새를 저장할때 그 냄새가 유효한 시간을 저장하는게 풀때 용이했다.

void remainSmell(int t)
{
	for (int i= 0; i < sharks.size(); i++)
	{
		Shark shark = sharks[i];
		if (shark.isAlive == false)
			continue;
		smell[shark.y][shark.x] = { i, t + K };
	}
}

그 외의 세세한 코드들은 전체코드를 참고하기 바란다.

---

코드

/*
시작 시간 : 13시 46분
종료 시간 : 16시
소요 시간 : 2시간 14분

문제 풀이 
1. shark 클래스를 만들어서 상어가 살아있는지 여부, 좌표, 방향값을 저장

2. dir vector를 만들어서 방향의 우선순위 파악 dir[상어의 인덱스][상어가 가지고 있는 방향][4가지의 방향]

3. 냄새는 <상어의 인덱스,  냄새가 유효한 시간>를 저장하는 배열으로 만들어놓음.

4. 시간이 <=1000까지 반복
 1. 상어 움직이기 
  (빈곳부터 우선순위 방향의 순서대로 찾아보고 빈곳이 없다면 자기 냄새가 있는곳을 찾아봄)

 2. 겹친 상어가 있다면 가장 작은 숫자를 가지는 상어를 제외하고 죽인다.
  (map이라는 비어있는 이차원 배열을 이용해서 겹치는 것들을 찾았습니다.)

 3. 냄새를 남기기

 4. 상어가 1번만 남아있는지 확인하여 1번만 남아있다면 answer값을 t값으로 갱신후 종료
*/
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

//idx, time순
pair<int, int> smell[20][20];
int map[20][20];
int M, N, K;
vector<vector<vector<int>>>dir;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
vector<Shark> sharks;

void Input()
{
	//map 입력
	cin >> N >> M >> K;
	sharks.resize(M);
	dir.resize(M);
	for (int i = 0; i < M; i++)
		dir[i].resize(4);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			int mapVal;
			cin >> mapVal;

			if (mapVal == 0)
				continue;
			
			Shark shark(i, j);
			sharks[mapVal - 1] = shark;
		}
	}

	//방향 입력
	for (int i = 0; i < M; i++)
	{
		int shDir;
		cin >> shDir;
		sharks[i].dir = shDir - 1;
	}

	//우선순위 입력
	for (int idx = 0; idx < M; idx++)
	{
		//방향 상 하 좌 우
		for (int d = 0; d < 4; d++)
		{
			dir[idx][d].resize(4);
			for (int i = 0; i < 4; i++)
			{
				cin >> dir[idx][d][i];
			}
		}
	}
}

void smellInit()
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			smell[i][j] = { -1, -1 };
		}
	}
}

void remainSmell(int t)
{
	for (int i= 0; i < sharks.size(); i++)
	{
		Shark shark = sharks[i];
		if (shark.isAlive == false)
			continue;
		smell[shark.y][shark.x] = { i, t + K };
	}
}

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

void MoveSharks(int currentTime)
{
	for (int i = 0; i < sharks.size(); i++)
	{
		Shark shark = sharks[i];

		if (shark.isAlive == false)
			continue;

		bool isMove = false;
		//빈곳 먼저
		for (int j = 0; j < 4; j++)
		{
			int cdir = dir[i][shark.dir][j] - 1;
			int ny = shark.y + dy[cdir];
			int nx = shark.x + dx[cdir];

			//범위가 넘는지 확인
			if (IsInRange(ny, nx) == false)
				continue;

			//냄새가 존재하는지 확인
			if (smell[ny][nx].first != -1 && currentTime <= smell[ny][nx].second)
				continue;

			isMove = true;
			shark.y = ny;
			shark.x = nx;
			shark.dir = cdir;
			sharks[i] = shark;
			break;
		}

		if (isMove == true)
			continue;

		//빈곳이 없을시에 자기 냄새가 있는 곳으로
		for (int j = 0; j < 4; j++)
		{
			int cdir = dir[i][shark.dir][j] - 1;
			int ny = shark.y + dy[cdir];
			int nx = shark.x + dx[cdir];

			//범위가 넘는지 확인
			if (IsInRange(ny, nx) == false)
				continue;

			//내 냄새인지 확인
			if (smell[ny][nx].first == i)
			{
				isMove = true;
				shark.y = ny;
				shark.x = nx;
				shark.dir = cdir;
				sharks[i] = shark;
				break;
			}
		}
	}
}

void mapInit()
{
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			map[i][j] = -1;
}

bool IsEndSituation()
{
	for (int i = 1; i < M; i++)
	{
		if (sharks[i].isAlive == true)
			return false;
	}
	return true;
}

void simulation()
{
	int answer = -1;
	int t = 0;
	smellInit();
	remainSmell(t);
	for (t = 1; t <= 1000; t++)
	{
		//상어 움직이기
		MoveSharks(t);

		//겹친 상어가 있는지 확인
		mapInit();
		for (int i = 0; i < sharks.size(); i++)
		{
			Shark& shark = sharks[i];
			if (shark.isAlive == false)
				continue;
			//겹쳤는데  잡아먹힘
			if (map[shark.y][shark.x] < i && map[shark.y][shark.x] != -1 )
			{
				shark.isAlive = false;
			}
			//그자리에 배치
			else
			{
				map[shark.y][shark.x] = i;
			}
		}

		//냄새 남기기
		remainSmell(t);

		//1번 상어만 남았는지 확인
		if (IsEndSituation() == true)
		{
			answer = t;
			break;
		}
	}
	cout << answer << endl;
}

int main()
{
	Input();
	simulation();
	return 0;
}

---

상어의 데이터값을 갱신을 안해주는 실수를 저질러서 오래걸렸다.