<Baekjoon> #19237 구현_어른 상어

#19237 어른 상어

🦈1. Struct 만들기

struct SHARK 정의

• 상어는 위치와 방향, 그리고 각 방향으로 향하고 있을 때마다 우선 순위 방향을 가지고 있다
• 같은 칸에 여러 상어가 있을 경우 가장 낮은 번호의 상어만 남기고 죽기 때문에 상어가 살아 있는지 아닌지 판단하는 변수 필요

  struct SHARK {
      int y, x;
      int dir;
      int p[5][4];
      bool alive = true;
  };
  vector<SHARK> shark;

struct MAP_INFO 정의

• 상어들이 움직이고 난 후 한 칸에는 여러 상어가 있다
• 한 칸에는 상어가 뿌린 냄새와 냄새가 사라지기까지 남은 시간이 저장된다

  struct MAP_INFO {
      vector<int> v;
      int scent_time=0;
      int scent_host=0;
  };
  MAP_INFO map[MAX][MAX];

🦈2. Input Data

• 먼저 map의 정보를 받아오며 map에 상어의 번호를 저장하고 상어의 위치를 저장한다
• 각 map의 냄새의 주인을 저장하는 변수와 남은 시간은 0으로 초기화 한다
  (이 부분을 생략하고 구조체를 선언할 때 초기화를 했더니 계속 오류가 났다)

	//input shark position & scent
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int n;  cin >> n; 
			if (n != 0) {
				map[i][j].v.push_back(n);
				shark[n].y = i;
				shark[n].x = j;
			}
			map[i][j].scent_host = 0;
			map[i][j].scent_time = 0;
		}
	}

• 다음으로 각 상어의 현재 방향을 입력 받는다

	//input shark direction
	for (int i = 1; i <= M; i++) {
		int dir; 
		cin >> dir;
		shark[i].dir = dir;
	}

• 1번 상어부터 순서로 1,2,3,4번 방향일 때 이동하는 방향의 우선순위를 저장한다

	//input shark's priority direction
	for (int i = 1; i <= M; i++) {
		for (int dir = 1; dir <= 4; dir++) {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			shark[i].p[dir][0] = a;
			shark[i].p[dir][1] = b;
			shark[i].p[dir][2] = c;
			shark[i].p[dir][3] = d;
		}
	}

🦈3. Setting Smell

• 위에서 처음 map에 데이터를 입력할 때, 냄새의 주인과 냄새가 사라지기까지 남은 시간은 0으로 초기화를 해두었다
• 이 함수에서는 남은 냄새의 시간과 냄새의 주인을 업데이트 한다
• 살아있는 모든 상어가 움직인 위치를 조사해 해당 위치에 냄새와 냄새가 사라지기까지 남은 시간을 업데이트 한다
• time은 게임이 시작되고 흐른 시간을 나타내며 scent_time은 현재 시간 (time)을 기준으로 k초 후까지만 유효하다

//time=current time
void setting_smell(int time) {
	for (int i = 1; i <= M; i++) {
		if (shark[i].alive == false) continue;

		int y = shark[i].y;
		int x = shark[i].x;
		//현재 시간을 기준으로 k초 후 까지만 유효함
		map[y][x].scent_time = time + K; 
		map[y][x].scent_host = i;
	}
}

🦈4. Move Shark

• 먼저 맵의 각 칸에 있는 상어를 비워준다 (모든 살아있는 상어가 움직여서 새로운 칸으로 이동하기 때문)

	for (int i = 1; i <= M; i++) {
		if (shark[i].alive == false) continue;
		int y = shark[i].y;
		int x = shark[i].x;
		map[y][x].v.clear();
	}

• 인접한 네 칸중 아무 냄새가 없는 칸이 있는 경우 그 칸으로 이동
• 이동할 곳의 좌표가 (ny, nx)일 때, if (map[ny][nx].scent_time<= time) : 이동할 곳의 냄새의 시간이 현재 시간 time과 같거나 작다는 뜻은 이동 했을 때 해당 칸의 냄새는 사라진다는 의미이고 따라서 해당 칸은 빈 칸이 된다는 뜻이다
  (상어가 모두 움직이고, 같은 칸에 있는 상어가 죽고 나서 1초가 된다. 처음에는 0초에서 시작한다)
• 그런 칸이 없는 경우 현재 자신의 방향을 기준으로 우선순위가 높은 칸부터 탐색해서 자신의 냄새가 있는 칸에 넣어준다
• 위 탐색 과정을 동시에 진행해주고 bool flag 변수를 두어 인접한 아무 냄새가 없는 칸을 찾았을 경우에는 true로 바꾸어 준다 (자신의 냄새가 있는 칸으로 이동하지 않아도 된다는 의미로)
• 인접한 아무 냄새가 없는 칸을 못 찾았을 경우에는 위에서 탐색을 할 때 같이 구해놓았던 근처에 있는 자신의 냄새가 있는 칸으로 이동한다

	/*
	2. 움직이려는 칸에 아무 냄새가 없는 경우, 
	자신의 냄새가 있는 경우를 동시에 조사하고 
	빈칸에 넣지 못했을 경우 자신의 냄새가 있는 칸에 넣어줌
	*/
	for (int i = 1; i <= M; i++) {
		if (shark[i].alive == false) continue;
		int y = shark[i].y;
		int x = shark[i].x;
		int dir = shark[i].dir;

		int tmpX, tmpY, tmpD;
		tmpX = tmpY = tmpD = -1;

		bool flag = false;

		for (int d = 0; d < 4; d++) {
			//현재 방향 dir을 기준으로 d번째 우선 순위
			int nDir = shark[i].p[dir][d]; 
			int ny = y + dy[nDir];
			int nx = x + dx[nDir];

			if (ny <1 || nx < 1 || ny >N || nx > N) continue;
			
			//scnet_time이 현재시간보다 작거나 같다는 뜻은 비었다는 뜻
			if (map[ny][nx].scent_time<= time) {
				flag = true;
				map[ny][nx].v.push_back(i);
				shark[i].y = ny;
				shark[i].x = nx;
				shark[i].dir = nDir;
				break;
			}
			else {
				//우선 순위가 높은 순으로 조사했을 때 자기 칸
				if (map[ny][nx].scent_host == i) {
					//자기보다 우선순위가 높은 방향에서 자기 칸을 아직 못 찾았을 경우
					if (tmpX == -1) {
						tmpY = ny;
						tmpX = nx;
						tmpD = nDir;
					}
				}
			}
		}
		if (flag==false) {
			map[tmpY][tmpX].v.push_back(i);
			shark[i].y = tmpY;
			shark[i].x = tmpX;
			shark[i].dir = tmpD;
		}
	}

🦈5. Killing Shark

• 한 칸에 상어가 두 마리 이상인 경우 작은 상어만 살아남는다
• map[y][x].v에 있는 상어들의 번호를 정렬해 가장 앞에 있는 상어만 살리고 나머지는 죽인다

		if (map[y][x].v.size() >= 2) {
			sort(map[y][x].v.begin(), map[y][x].v.end());
			int small = map[y][x].v[0];
			for (int i = 1; i < map[y][x].v.size(); i++) {
				int idx = map[y][x].v[i];
				shark[idx].alive = false;
			}
			map[y][x].v.clear();
			map[y][x].v.push_back(small);
			map[y][x].scent_host = small;
		}

Source Code

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

using namespace std;

const int MAX = 21;
int N, M, K;

int dy[] = {0, -1, 1, 0 ,0};
int dx[] = {0, 0,0, -1, 1};

struct SHARK {
	int y, x;
	int dir;
	int p[5][4];
	bool alive = true;
};
vector<SHARK> shark;

struct MAP_INFO {
	vector<int> v;
	int scent_time=0;
	int scent_host=0;
};
MAP_INFO map[MAX][MAX];

//time=current time
void setting_smell(int time) {
	for (int i = 1; i <= M; i++) {
		if (shark[i].alive == false) continue;

		int y = shark[i].y;
		int x = shark[i].x;
		//현재 시간을 기준으로 k초 후 까지만 유효함
		map[y][x].scent_time = time + K; 
		map[y][x].scent_host = i;
	}
}

void move_shark(int time) {
	//1. 맵의 각 칸에 있는 상어를 비워줌
	for (int i = 1; i <= M; i++) {
		if (shark[i].alive == false) continue;
		int y = shark[i].y;
		int x = shark[i].x;
		map[y][x].v.clear();
	}
	/*
	2. 움직이려는 칸에 아무 냄새가 없는 경우, 
	자신의 냄새가 있는 경우를 동시에 조사하고 
	빈칸에 넣지 못했을 경우 자신의 냄새가 있는 칸에 넣어줌
	*/
	for (int i = 1; i <= M; i++) {
		if (shark[i].alive == false) continue;
		int y = shark[i].y;
		int x = shark[i].x;
		int dir = shark[i].dir;

		int tmpX, tmpY, tmpD;
		tmpX = tmpY = tmpD = -1;

		bool flag = false;

		for (int d = 0; d < 4; d++) {
			//현재 방향 dir을 기준으로 d번째 우선 순위
			int nDir = shark[i].p[dir][d]; 
			int ny = y + dy[nDir];
			int nx = x + dx[nDir];

			if (ny <1 || nx < 1 || ny >N || nx > N) continue;
			
			//scnet_time이 현재시간보다 작거나 같다는 뜻은 비었다는 뜻
			if (map[ny][nx].scent_time<= time) {
				flag = true;
				map[ny][nx].v.push_back(i);
				shark[i].y = ny;
				shark[i].x = nx;
				shark[i].dir = nDir;
				break;
			}
			else {
				//우선 순위가 높은 순으로 조사했을 때 자기 칸
				if (map[ny][nx].scent_host == i) {
					//자기보다 우선순위가 높은 방향에서 자기 칸을 아직 못 찾았을 경우
					if (tmpX == -1) {
						tmpY = ny;
						tmpX = nx;
						tmpD = nDir;
					}
				}
			}
		}
		if (flag==false) {
			map[tmpY][tmpX].v.push_back(i);
			shark[i].y = tmpY;
			shark[i].x = tmpX;
			shark[i].dir = tmpD;
		}
	}
}

void killing_shark(int time) {
	for (int i = 1; i <= M; i++) {
		if (shark[i].alive == false) continue;
		int y = shark[i].y;
		int x = shark[i].x;
		//한 칸에 상어 두 마리 이상인 경우 작은 상어만 살아 남음
		if (map[y][x].v.size() >= 2) {
			sort(map[y][x].v.begin(), map[y][x].v.end());
			int small = map[y][x].v[0];
			for (int i = 1; i < map[y][x].v.size(); i++) {
				int idx = map[y][x].v[i];
				shark[idx].alive = false;
			}
			map[y][x].v.clear();
			map[y][x].v.push_back(small);
			map[y][x].scent_host = small;
		}
	}
}

void input() {
	cin >> N >> M >> K;
	shark = vector<SHARK>(M+1);

	//input shark position & scent
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int n;  cin >> n; 
			if (n != 0) {
				map[i][j].v.push_back(n);
				shark[n].y = i;
				shark[n].x = j;
			}
			map[i][j].scent_host = 0;
			map[i][j].scent_time = 0;
		}
	}
	//input shark direction
	for (int i = 1; i <= M; i++) {
		int dir; 
		cin >> dir;
		shark[i].dir = dir;
	}
	//input shark's priority direction
	for (int i = 1; i <= M; i++) {
		for (int dir = 1; dir <= 4; dir++) {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			shark[i].p[dir][0] = a;
			shark[i].p[dir][1] = b;
			shark[i].p[dir][2] = c;
			shark[i].p[dir][3] = d;
		}
	}
}

bool check_vaild() {
	for (int i = 2; i <= M; i++) 
		if (shark[i].alive == true) return false;
	return true;
}

int solution() {
	int answer = -1;

	for (int time = 0; time < 1001; time++) {
		if (check_vaild()) {
			answer = time;
			break;
		}
		setting_smell(time);
		move_shark(time);
		killing_shark(time);

	}
	return answer;
}

int main() {
	input();
	cout<<solution()<<endl;

	return 0;

}