19237번 어른상어

www.acmicpc.net/problem/19237

 

 

 

 

 

 

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

#include <bits/stdc++.h>

using namespace std;

#define SHARK_MAX 1010
#define BOARD_MAX_SIZE 22

// 1:위, 2:아래, 3:왼, 4:오

// N:배열 크기, M:상어 수(1~M), K:시간
int N, M, K;
// 1~M번 상어의 위치(y, x)
pair<int, int> shark_position[SHARK_MAX];
// 냄새에 대한 정보 배열(상어 번호, 시간)
pair<int, int> smell[BOARD_MAX_SIZE][BOARD_MAX_SIZE];
// n번 상어의 현재 방향
int now_shark_direction[SHARK_MAX];
// n번 상어의 현재 방향에 따른 우선순위
vector<int> priority_direction[SHARK_MAX][5];
// 한 칸 이동하기 위한 변수
int dy[5] = { 0, -1, 1, 0, 0 };
int dx[5] = { 0, 0, 0, -1, 1 };
// 살아있는지(?) 변수
bool isLive[SHARK_MAX];
// 상어 위치 지도 및 임시 지도
int Map[BOARD_MAX_SIZE][BOARD_MAX_SIZE];
int temp[BOARD_MAX_SIZE][BOARD_MAX_SIZE];

bool chk()
{
	for (int i = 2; i <= M; i++) {
		if (isLive[i]) {
			return false;
		}
	}

	return true;
}

int simulation()
{
	for (int time = 1; time <= 1000; time++) {
		map<pair<int, int>, int> m;
		memset(temp, 0, sizeof(temp));

		for (int i = M; i >= 1; i--) {
			if (!isLive[i]) {
				continue;
			}

			// 상어 위치 및 현재 바라보고 있는 방향
			int r = shark_position[i].first;
			int c = shark_position[i].second;
			int now_direction = now_shark_direction[i];

			// 자신의 냄새가 있는 (이동할) 칸 위치 저장
			int sr = 0, sc = 0;

			bool isExistPd = false;

			// 우선순위 처리 표시
			bool temp_chk = false;
			int temp_pd = 0;

			// 상어의 현재 방향에 따른 우선순위 방향
			for (int pd : priority_direction[i][now_direction]) {
				int y = r + dy[pd];
				int x = c + dx[pd];

				if (y < 0 || y >= N || x < 0 || x >= N) {
					continue;
				}

				if (smell[y][x].first != NULL && smell[y][x].second != NULL) {
					if (!temp_chk && smell[y][x].first == i) {
						temp_chk = true;
						temp_pd = pd;
						sr = y;
						sc = x;
					}			
					continue;
				}

				// 갈 수 있는 방향 표시(냄새가 없는 칸)
				isExistPd = true;

				// 상어 위치 및 방향 갱신
				shark_position[i] = { y, x };
				now_shark_direction[i] = pd;

				if (temp[y][x] != 0) {
					isLive[temp[y][x]] = false;
				}

				temp[y][x] = i;

				break;
			}

			// 자신의 냄새가 있는 칸으로 이동
			if (!isExistPd) {
				if (temp[sr][sc] != 0) {
					isLive[temp[sr][sc]] = false;
				}
				temp[sr][sc] = i;
				shark_position[i] = { sr, sc };
				now_shark_direction[i] = temp_pd; // 이 부분을 실수.
			}
		}

		// 기존 냄새 시간 -1 감소
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (smell[i][j].first != NULL && smell[i][j].second != NULL) {
					// (상어 번호, 시간)
					if (--smell[i][j].second == 0) {
						smell[i][j] = { NULL, NULL };
					}
				}
			}
		}

		// 새로운 냄새 갱신
		for (int i = 1; i <= M; i++) {
			if (!isLive[i]) {
				continue;
			}

			int y = shark_position[i].first;
			int x = shark_position[i].second;

			smell[y][x].first = i;
			smell[y][x].second = K;
		}

		// 1번 상어만 격자에 남겨져 있는지 체크
		if (chk()) {
			return time;
		}
	}

	return -1;
}

void init()
{
	scanf("%d %d %d", &N, &M, &K);

	int init_input = 0;

	// 초기 상어 위치 정보
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			smell[i][j] = { NULL, NULL };
			
			scanf("%d", &init_input);
			Map[i][j] = init_input;

			if (init_input != 0) {
				shark_position[init_input] = { i, j };
				// 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다.
				smell[i][j] = { init_input , K }; // {상어 번호, 시간}
				isLive[init_input] = true; // 살아있음 표시
			}
		}
	}

	// 각 상어의 초기 현재 방향
	for (int i = 1; i <= M; i++) {
		scanf("%d", &init_input);
		now_shark_direction[i] = init_input;
	}

	// 상어의 현재 방향에 따른 우선순위
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 1; k <= 4; k++) {
				scanf("%d", &init_input);
				priority_direction[i][j].push_back(init_input);
			}
		}
	}
}

int main()
{
	//freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
	cin.tie(0);

	init();
	
	printf("%d\n", simulation());

	return 0;
}

 

 

 

 

 

 

 

colorscripter.com/s/OSZjETB

공유된 코드 - Color Scripter

 

 

 

 

 

109번 째 줄에서 실수를 했었는데 자신의 냄새가 있는 칸으로 이동하는 방향은 현재 자신의 방향에 대한 역방향이 아니다. 처음에는 현재 자신의 방향에 대한 역방향으로 무조건 저장했었다. 자신의 냄새가 있는 칸의 방향은 상하좌우 모두 될 수 있으므로, 우선순위 방향에 대한 for문에서도 따로 저장해야한다.

 

그리고 상어를 큰 번호부터 for문을 수행하면, 잡아 먹히는 과정에 대한 로직이 크게 감소한다.(덮어 씌우면 됨)