백준 19237 어른 상어 - C++

https://forswdev.tistory.com/entry/%EB%B0%B1%EC%A4%80-19236-%EC%B2%AD%EC%86%8C%EB%85%84-%EC%83%81%EC%96%B4-C

백준 19236 청소년 상어 - C++

청소년 상어가 진화했다.

마찬가지로 삼성스타일의 문제이므로

길고 자세한 시뮬레이션을 요구한다.

 

 

문제를 읽고 나면 역시나

규칙이 자세하고 복잡하여 머리가 어지럽지만

한 번 정리해보자.

1. 상어는 자신의 자리에 k 시간 유지되는 냄새를 남긴다.

2. 상어가 이동할 때는 방향과 냄새만이 중요하고 다른 상어가 같은 턴에 들어오는지는 중요하지 않다.

3. 가장 낮은 번호의 상어가 가장 세다.

4. 상어마다 우선순위 방향이 다르다.

5. 1번 상어만 남을 때까지 걸리는 시간을 출력한다 = 턴 횟수를 출력한다.

6. 1000번 넘어도 남아있을 경우(가령 동선이 평행하다던가) -1을 출력한다.

 

기본적으로 우선순위/현재상어위치/냄새남은시간를 저장해야 한다.

저장하고 queue 에 상어들을 넣고 턴마다 기록하면서 위 조건에 맞게 제한을 건다.

조건이 자세하고 복잡하므로 조건문에 신경을 써서 작성하시면 됩니다.

리팩을 하지 않아서 조금 더럽습니다만 충분히 볼 만한 것 같습니다.

#include <stdio.h>
#define DEBUG 0
#define INF 987654321
int N, M, K;
int Map[21][21];
int visited[21][21][3];//0=냄새뿌린시간 1=현재 있는 상어 종류 2 0=돌아가지 않은 경우 1돌아간경우
int s_num;
int pri[400 + 1][4 + 1][4 + 1];// M번상어 dir 일 때 우선순위
int dead[401];
typedef struct sh {
	int y, x, power, dir,time;
}SHARK;
SHARK shark[401];
int dy[] = { 0,-1,1,0,0 };
int dx[] = { 0,0,0,-1,1 };
//0123 상하좌우

SHARK queue[401 * 1000+10];
int wp, rp;
void pop() { rp++; }
void push(SHARK x) { queue[wp++] = x; }
int empty() { return wp == rp; }
SHARK front() { return queue[rp]; }
int curtime = 0;

int simulate() {
	while (!empty()) {
		SHARK cur = front(); pop();
		if (s_num <= 1) return cur.time+1;
		if (cur.time >1000) break;
		if (dead[cur.power]) continue;
		//이슈 : 겹칠 경우 방출되는 상어 관리
		int isEmpty = 0, isSame = 0, isCut=0;
		int nextdir, ny, nx,j,i;
		//주변 탐색
		for ( j = 0; j < 2; j++) {
			for (i = 1; i <= 4; i++) {
				nextdir = pri[cur.power][cur.dir][i];
				ny = cur.y + dy[nextdir];
				nx = cur.x + dx[nextdir];
				if (ny >= N || ny < 0 || nx >= N || nx < 0) continue;
				//빈곳찾기
				if (j == 0) {
					//완전 빈 경우
					if (visited[ny][nx][0] == INF) {
						isEmpty = 1;
						break;
					}
					//냄새가 사라진 경우
					if (visited[ny][nx][0] <= cur.time) {
						isEmpty = 1;
						break;
					}
					//같은 시점에 동시에 도착하는 경우
					if (visited[ny][nx][0] == cur.time + K + 1) {
						if (visited[ny][nx][2] == 0) {
							isCut= 1;
							break;
						}
					}
				}
				//없으면 자기 냄새로 돌아가기
				else if (j == 1) {
					if (visited[ny][nx][1] == cur.power && visited[ny][nx][0] < cur.time+K) {
						isSame = 1;
						break;
					}
				}
			}
			if (isEmpty || isSame || isCut) break;
		}
		if (isCut) {
			if (DEBUG) printf("DEAD : %d\n", cur.power);
			if (dead[cur.power] == 0) {
				dead[cur.power] = 1;
				s_num--;
			}
			if (s_num <= 1) {
				if (cur.time+1 > 1000) return -1;
				return cur.time + 1;
			}
			continue;
		}
		if (DEBUG) {
			if (isEmpty == 0 && isSame == 0) {
				printf("ERROR\n");
			}
		}
		//
		SHARK tmp = { ny,nx,cur.power, nextdir, cur.time+1 };
		if (isEmpty) {
			visited[ny][nx][0] = cur.time + K + 1;
			visited[ny][nx][1] = cur.power;
			visited[ny][nx][2] = 0;
			push(tmp);
			
		}
		//돌아간경우
		else if (isSame) {
			visited[ny][nx][0] = cur.time + K + 1;
			visited[ny][nx][1] = cur.power;
			visited[ny][nx][2] = 1;
			push(tmp);
		}
		if (DEBUG) {
			if (curtime == cur.time - 1) {
				curtime++;
				printf("\n");
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						printf("%9d ", visited[i][j][0]);
					}
					printf("\n");
				}
			}
		}



	}

	return -1;
}


int solve() {
	return simulate();
}

int main() {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j][0] = INF;
			visited[i][j][1] = INF;
			visited[i][j][2] = INF;
			scanf("%d", &Map[i][j]);

			//상어들어오면 번호별로 저장
			if (Map[i][j]) {
				shark[Map[i][j]].y = i;
				shark[Map[i][j]].x = j;
				shark[Map[i][j]].power = Map[i][j];
				shark[Map[i][j]].time = 0;
				visited[i][j][0] = K; 
				visited[i][j][1] = Map[i][j];
				visited[i][j][2] = 0;
			}
		}
	}
	for (int i = 1; i <= M; i++) {
		scanf("%d", &shark[i].dir);
		push(shark[i]);
	}
	s_num = M;
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= 4; j++) {
			for (int k = 1; k <= 4; k++) {
				scanf("%d", &pri[i][j][k]);
			}
		}
	}
	int ans = solve();
	printf("%d\n", ans);
}