[백준 19237] 어른 상어

아악 ~~~ 나색기~~~~ 완전 기특해~~~~

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

19237번: 어른 상어

#include <cstdio>
#include <queue>
int N, M, K;
int Shark[20 + 2][20 + 2];
int lookup[400 + 2][4 + 2][4 + 2];

struct _st
{
	int x, y;
	int dir;
	bool alive;
}Info[400 + 2];


struct _ct
{
	int idx;
	int time;
}Smell[20 + 2][20 + 2];



void debug()
{
	printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
	for (int i = 1; i <= M; i++) {
		printf("%d %d %d %d\n", Info[i].x, Info[i].y, Info[i].dir, Info[i].alive);
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%d", Smell[i][j].time);
		}
		printf("\n");
	}

}



void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &Shark[i][j]);
			if (Shark[i][j] != 0) {
				Info[Shark[i][j]] = { i, j, -1, true };	// 정보갱신
				Smell[i][j] = { Shark[i][j], K };			// s번째 상어가 냄새 뿌림
			}	
		}
	}
	for (int i = 1; i <= M; i++) {
		int d = 0;
		scanf("%d", &d);
		Info[i].dir = d;
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int p = 1; p <= 4; p++) {
				scanf("%d", &lookup[i][j][p]);
			}
		}
	}
}


void kill_shark()
{
	std::fill(&Shark[0][0], &Shark[0][0] + sizeof(Shark) / sizeof(int), 0);
	for (int i = 1; i <= M; i++) {
		int x = Info[i].x;
		int y = Info[i].y;
		if (Shark[x][y] != 0) Info[i] = { -1, -1, -1, false };
		else Shark[x][y] = i;
	}
}



void move_shark()
{
	static int dir_x[5] = {0, -1, 1, 0, 0 };
	static int dir_y[5] = {0, 0, 0, -1, 1 };

	for (int i = 1; i <= M; i++) {
		if (Info[i].alive == false) continue;
		int x = Info[i].x;
		int y = Info[i].y;
		int dir = Info[i].dir;
		bool set = false;

		// 아무 냄새가 없는 칸의 방향으로 잡는다.
		for (int p = 1; p <= 4; p++) {
			int ndir = lookup[i][dir][p];
			int nx = x + dir_x[ndir];
			int ny = y + dir_y[ndir];
			
			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (Smell[nx][ny].idx != 0) continue;
			Info[i] = { nx, ny, ndir, true };
			set = true;
			break;
		}
		// 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다. 
		// 가능한 칸이 여러개라면 특정한 우선순위를 따른다. 
		if (set == false) {
			for (int p = 1; p <= 4; p++) {
				int ndir = lookup[i][dir][p];
				int nx = x + dir_x[ndir];
				int ny = y + dir_y[ndir];

				if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
				if (Smell[nx][ny].idx == i) {
					Info[i] = { nx, ny, ndir, true };
					break;
				}
			}
		}
	}
	kill_shark();
}



void del_smell()
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (Smell[i][j].time > 0) {
				Smell[i][j].time -= 1;
				if (Smell[i][j].time == 0) Smell[i][j].idx = 0;
			}
		}
	}
}

void put_smell()
{
	for (int i = 1; i <= M; i++) {
		if (Info[i].alive == false) continue;
		Smell[Info[i].x][Info[i].y] = {i, K};
	}
}




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



int simul()
{
	for (int time = 1; time <= 1000; time++) {
		move_shark();
		del_smell();
		put_smell();
		if (chk_onlyone()) return time;
		//debug();
	}
	return -1;

}

int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}

아 드디어 내힘으로 어른상어 풀었다. 진짜 대박이다

 

 

이전 풀이는 아래와 같다. 

더러웠고,,, 다신 만나지말자 제발,,,

#include <cstdio>
#include <vector>
int N, M, K;

struct _mt
{
	int no;			// 무슨 냄새가 남아있는지 
	int time;		// 몇분 남았는지 
	int is_shark;	// 상어 있는지 없는지 
}Smell[20 + 2][20 + 2];


struct _st
{
	int x, y;
	int dir;
	bool alive = true;
}Shark[400 + 2];


int lookup[400 + 2][4 + 2][4 + 2];

void debug()
{
	printf("========================================\n");
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			printf("%d ", Smell[i][j].is_shark);
		}
		printf("\n");
	}
	for (int i = 1; i <= M; i++) {
		printf("%d %d %d %d\n", Shark[i].x, Shark[i].y, Shark[i].dir, Shark[i].alive);
	}
}



void input()
{
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &Smell[i][j].is_shark);
			if (Smell[i][j].is_shark != 0) {
				Smell[i][j].no = Smell[i][j].is_shark;
				Smell[i][j].time = K;
				Shark[Smell[i][j].no].x = i;
				Shark[Smell[i][j].no].y = j;
			}
		}
	}
	for (int i = 1; i <= M; i++) {
		scanf("%d", &Shark[i].dir);
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= 4; j++) {		// 네 방향 
			for (int k = 1; k <= 4; k++) {	// 우선순위 네 개
				scanf("%d", &lookup[i][j][k]);
			}
		}
	}
}


void del_smell()
{
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (Smell[i][j].time > 0) Smell[i][j].time -= 1;
			if (Smell[i][j].time == 0) Smell[i][j].no = 0;	// 냄새는 상어가 K번 이동하고 나면 사라진다.  
		}
	}
}


void mv_shark()
{
	// 1상 2하 3좌 4우
	static int dir_x[5] = {0,  -1, 1, 0, 0 };
	static int dir_y[5] = {0,  0, 0, -1, 1 };

	for (int i = 1; i <= M; i++) {
		if (Shark[i].alive == false) continue;

		bool get_set = false;

		for (int p = 1; p <= 4; p++) {				// 1. 인접한 칸 중 아무 냄새가 없는 칸을 탐색한다, 
			int nd = lookup[i][Shark[i].dir][p];	// i번째 상어의 현재 방향의 우선순위 p
			int nx = Shark[i].x + dir_x[nd];
			int ny = Shark[i].y + dir_y[nd];

			if (nx < 1 || nx  > N || ny < 1 || ny > N) continue;
			if (Smell[nx][ny].time == 0) {		// 빈칸이라면 
				if (Smell[nx][ny].is_shark < i && Smell[nx][ny].is_shark != 0) {
					Smell[Shark[i].x][Shark[i].y].is_shark = 0;
					Shark[i].alive = false;		// 들어가는데, 해당 칸에 자기보다 작은 상어도 들어올 것이라면 죽음
					get_set = true;
					break;
				}
				Smell[Shark[i].x][Shark[i].y].is_shark = 0;
				Shark[i].x = nx;				// 상어정보 갱신한다. 
				Shark[i].y = ny;
				Shark[i].dir = nd;
				Smell[nx][ny].is_shark = i;			// 해당 상어가 그 칸에 들어갈 것이라고 표시만 해줌 
				get_set = true;
				break;
			}
		}
		if (get_set == false) {						// 2. 빈칸이 없어서 상어가 자리를 못잡은 경우 
			for (int p = 1; p <= 4; p++) {			// 자신의 냄새를 탐색한다.
				int nd = lookup[i][Shark[i].dir][p];
				int nx = Shark[i].x + dir_x[nd];
				int ny = Shark[i].y + dir_y[nd];

				if (nx < 1 || nx  > N || ny < 1 || ny > N) continue;
				if (Smell[nx][ny].no == i) {
					Smell[Shark[i].x][Shark[i].y].is_shark = 0;
					Shark[i].x = nx;
					Shark[i].y = ny;
					Shark[i].dir = nd;
					Smell[nx][ny].is_shark = i;
					get_set = true;
					break;
				}
			}
		}
	}
}



void put_smell()
{
	for (int i = 1; i<= N ;i++){
		for (int j = 1; j <= N; j++) {
			if (Smell[i][j].is_shark != 0) {
				Smell[i][j].no = Smell[i][j].is_shark;
				Smell[i][j].time = K;
			}
		}
	}
}




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



int simul()
{
	int time = 0;
	while (1) {
		//debug();
		mv_shark();
		del_smell();
		put_smell();
		time++;
		if (time > 1000) return -1;
		if (chk_leave()) return time;
	}
}


int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;

}

(머리를 써야하는) 시뮬레이션 문제이다. 나는 그냥 머리 안쓰고 구현하는 문제가 좋은디 ㅎㅋ

 

1. 상어가 동시에 움직이기는 하지만, 번호가 작을 수록 강력하므로 1번 상어부터 M번 상어까지 확인한다. 

2. "빈칸을 찾았다고 해서 바로 상어를 위치시키고 냄새를 뿌리면 안된다." 그러면 이후 번호의 상어들이 해당 칸이 빈칸이 아니라는 것을 알고, 다른 방향으로 도망갈 것이기 때문이다.

따라서 해당 칸에 번호가 작은 상어를 위치시킬 것이라는 표시만 해놓고, 만약 이후 상어가 해당 칸으로 들어오려고 할 때 기존의 상어 번호보다 크면 잡아먹히도록 구현한다. 

3. 빈칸이 없어서 상어가 자리를 차지하지 못한 경우, 자신의 냄새가 위치한 칸을 찾아야 한다. 

우선순위에 따라 루프를 돌리면서 찾으면 바로 위치시켜 준다. 

4. 상어 이동이 끝나면 1초가 지났으므로 냄새를 없애주고(del_smell), 상어가 위치한 곳에 냄새를 남기고 시간을 갱신(put_smell)한다.