백준 19237 : 어른 상어 C++

www.acmicpc.net/problem/19237

19237번: 어른 상어

풀이

1. 상어는 일단 shark라는 struct 만들어서 관리

 -> 생존 여부

 -> 현재 위치, 방향

 -> 방향 우선순위들

 

2. map은 두개만들어서 관리

 1) 상어들

 2) 채취 정보

  -> 누가 남겼는지, 몇턴 남았는지

 

3. 입력 다 받고 while문 돌린다. 탈출하는건 두가지!

 1) 상어가 1번만 남음

 2) 1000 이상! // 초과 아니다!!!!!!!!!!

      if (result > 1000) -> 이거로 했다가 30분 날려먹음

 

4. while 문 구성

 1) 지금 상어 위치에 채취 남기기

 2) 상어들 이동! ( 이때 겹치면 젤 큰놈만 살리고 그러면 된다 )

 3) 채취 다 -1

 4) result++ (몇턴 지났는지 여부)

 5) 탈출 조건 만족하는지 체크

 

 

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

struct shark {
	int alive;
	int r, c, way;//지금 위치랑 방향
	int ways[4][4];//방향에 대한 우선순위
};
int map[21][21];//상어 위치
int back_up[21][21];
pair<int,int> map_smell[21][21];//채취 정보!!  어떤 상어, 남은 시간
shark sharks[401];
int n, m, k;
//n은 지도 m은 상어 마릿수 k는 냄새 지속시간


int d_r[4] = { -1,1,0,0 };//상 하 좌 우
int d_c[4] = { 0,0,-1,1 };


void move_shark()
{
	memset(back_up, 0, sizeof(back_up));
	for (int i = 1; i <= m; i++)
	{
		if (sharks[i].alive == 0)//죽은놈 재껴
			continue;

		int flag = 0;
		shark temp = sharks[i];

		//냄새 없는 칸
		for (int k = 0; k < 4; k++)
		{
			int new_r = temp.r + d_r[temp.ways[temp.way][k]];//지금 방향의 우선순위 순서대로
			int new_c = temp.c + d_c[temp.ways[temp.way][k]];

			if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= n)
				continue;

			if (map_smell[new_r][new_c].second == 0)//채취없는 칸이면 이동!!
			{
				sharks[i].r = new_r;
				sharks[i].c = new_c;
				sharks[i].way = temp.ways[temp.way][k];

				if (back_up[new_r][new_c] == 0)//아무도 없어!
				{
					back_up[new_r][new_c] = i;
					back_up[temp.r][temp.c] = 0;
					flag = 1;
					break;
				}
				else if( back_up[new_r][new_c] !=0)
				{
					//다음에 들어올 놈이 무조건 숫자 큼
					sharks[i].alive = 0;
					flag = 1;
					break;
				}
			}
		}

		if (flag == 1)
			continue;

		//냄새 없는칸 없으면!
		for (int k = 0; k < 4; k++)
		{
			int new_r = temp.r + d_r[temp.ways[temp.way][k]];//지금 방향의 우선순위 순서대로
			int new_c = temp.c + d_c[temp.ways[temp.way][k]];

			if (new_r < 0 || new_c < 0 || new_r >= n || new_c >= n)
				continue;

			if (map_smell[new_r][new_c].first == i)//내가 남긴 채취
			{
				sharks[i].r = new_r;
				sharks[i].c = new_c;
				sharks[i].way = temp.ways[temp.way][k];

				if (back_up[new_r][new_c] == 0)//아무도 없어!
				{
					back_up[new_r][new_c] = i;
					back_up[temp.r][temp.c] = 0;
					flag = 1;
					break;
				}
				else if (back_up[new_r][new_c] != 0)
				{
					//다음에 들어올 놈이 무조건 숫자 큼
					sharks[i].alive = 0;
					flag = 1;
					break;
				}
			}
		}

	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			map[i][j] = back_up[i][j];

}


int main()
{
	memset(map_smell, 0, sizeof(map_smell));
	memset(map, 0, sizeof(map));
	int a;
	cin >> n >> m >> k;

	for(int i=0;i<n;i++)
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (map[i][j] != 0)
			{
				sharks[map[i][j]].r = i;
				sharks[map[i][j]].c = j;
			}
		}

	for (int i = 1; i <= m; i++)
	{
		cin >> a;
		sharks[i].way = a - 1;
		sharks[i].alive = 1;
	}

	for (int i = 1; i <= m; i++)
	{
		for(int j=0;j<4;j++)
			for (int f = 0; f < 4; f++)
			{
				cin >> a;
				sharks[i].ways[j][f] = a - 1;
			}
	}


	int result = 0;

	while (true)
	{
		

		//지금 자리에 채취 남기기
		for (int i = 1; i <= m; i++)
		{
			if (sharks[i].alive == 0)//죽은 놈이면 패쓰요
				continue;
			//i 번째 상어가 채취 남겨요~
			map_smell[sharks[i].r][sharks[i].c].first = i;
			map_smell[sharks[i].r][sharks[i].c].second = k;
		}

		//이동 + 방향 바꿔주기
		move_shark();

		//채취 다 마이너스 1!
		for(int i=0;i<n;i++)
			for (int j = 0; j < n; j++)
			{
				if (map_smell[i][j].second != 0)
				{
					map_smell[i][j].second--;
					if (map_smell[i][j].second == 0)
					{
						map_smell[i][j].first = 0;
					}
				}
			}

		result++; //한턴 지나면!

		int flag = 0;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
			{
				if (map[i][j] != 0 && map[i][j] != 1)
					flag = 1;
			}

		if (flag == 0)//상어 한마리만 남는경우!
			break;

		if (result >= 1000)//1000넘어가면 바아로 -1
		{
			cout << -1 << endl;
			return 0;
		}
	}

	cout << result << endl;

	return 0;
}