[백준] 19237번: 어른 상어

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

19237번: 어른 상어

 

나머지 예제 생략

 

 

 

문제 이해

큰 틀을 잡아보면, 

1. 상어가 냄새를 남긴다

2. 상어가 이동한다

3. 겹치는 위치에 상어가 있으면 작은 상어만 남기고 다른 상어는 죽인다

4. 상어가 1번만 남았는지 확인한다 

 

상어의 흔적을 남길 맵을 정의해야 하는데, 나는 smell_map과 no_map을 두었다.

smell_map은 냄새의 수명이 저장되고, no_map은 냄새를 남긴 상어 번호가 저장되어 있는 맵이다.

 

그리고 상어를 저장할 배열을 만든다.

상어는 구조체로 구현하는데 위치와 방향, 살아있는지 여부를 저장한다.

 

Leave_Smell()

우선 시간이 지났으니까 냄새를 줄인다. (어차피 처음엔 냄새가 없으니까 상관이 없다.)

그냥 상어 배열을 돌면서 smell_map과 no_map에 상어 위치에 추가해주면 된다.

void Leave_Smell(void) {
	// 냄새 남기기
	int y, x;
	Smell_Decrease();
	for (int i = 1; i <= M; i++) {
		if (shark[i].l == 0) continue;
		y = shark[i].y;
		x = shark[i].x;
		no_map[y][x] = i;
		smell_map[y][x] = K;
	}
}

Shark_Move()

상어가 자기 방향에 맞춰 움직인다.

우선 냄새가 없는 칸을 찾는다. 4방향을 우선순위에 맞춰서 바꿔가면서 냄새 없는 칸이 있으면 거기로 이동하고 flag를 1로 바꿔준다.

만약 위에서 냄새 없는 칸을 못찾았으면 (flag == 0) 위와 같은 방식으로 4방향을 탐색하며 가능한 칸을 찾아 이동한다

void Shark_Move(void) {
	int y, x, d, ny, nx, nd;
	for (int i = 1; i <= M; i++) {
		if (shark[i].l == 0) continue;
		int flag = 0;
		int y = shark[i].y;
		int x = shark[i].x;
		int d = shark[i].d;
		for (int j = 0; j < 4; j++) {
			// a. 냄새 없는 곳 우선
			nd = priority[i][d][j];
			ny = y + dy[nd];
			nx = x + dx[nd];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (smell_map[ny][nx] != 0) continue;
			flag = 1;
			shark[i].y = ny, shark[i].x = nx, shark[i].d = nd;
			break;
		}
		if (flag == 1) continue;
		for (int j = 0; j < 4; j++) {
			// b. 본인 냄새인 곳
			nd = priority[i][d][j];
			ny = y + dy[nd];
			nx = x + dx[nd];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (no_map[ny][nx] != i) continue;
			flag = 1;
			shark[i].y = ny, shark[i].x = nx, shark[i].d = nd;
			break;
		}
	}
}

Shark_Out()

겹치는 상어들을 죽인다.

맵에다가 상어를 하나하나 표시한다.

만약에 맵에 들어가려고 하는데, 거기에 상어가 있으면 지금 넣으려는 상어보다 no가 큰지 본다.

크면 상어가 죽었다고 표시하고, 아니면 그 맵에 있는 상어를 죽이고 이 상어를 넣는다.

void Shark_Out(void) {
	memset(map, 0, sizeof(map));
	for (int i = 1; i <= M; i++) {
		if (shark[i].l == 0) continue;
		if (map[shark[i].y][shark[i].x] != 0) {
			// 여기 있는 애랑 경쟁 -> 한 마리는 죽음
			if (map[shark[i].y][shark[i].x] < i) {
				// i가 죽음
				shark[i].l = 0;
			}
			else {
				shark[map[shark[i].y][shark[i].x]].l = 0;
				map[shark[i].y][shark[i].x] = i;
			}
			scnt--;
		}
		else {
			map[shark[i].y][shark[i].x] = i;
		}
	}
}

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 20
#define MAXM 400

int N, M, K;
//typedef struct {
//	int no; // 상어 번호
//	int l; // 남은 냄새 수명
//}SMELL;
//SMELL smell[MAXN + 5][MAXN + 5];
int smell_map[MAXN + 5][MAXN + 5];
int no_map[MAXN + 5][MAXN + 5];
int map[MAXN + 5][MAXN + 5];
typedef struct s{
	int y, x, d, l;
}SHARK;
SHARK shark[MAXM + 5];
int scnt;
int priority[MAXM][4][4];

int dy[] = { -1, 1, 0, 0 }; // 위, 아래, 왼쪽, 오른쪽
int dx[] = { 0, 0, -1, 1 };

void Get_Input(void) {
	scanf("%d %d %d", &N, &M, &K);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++){
			scanf("%d", &map[i][j]);
			if (map[i][j] != 0) {
				shark[map[i][j]].y = i, shark[map[i][j]].x = j;
				shark[map[i][j]].l = 1;
				map[i][j] = 0;
			}
		}
	}
	for (int i = 1; i <= M; i++) {
		scanf("%d", &shark[i].d);
		shark[i].d--;
	}
	scnt = M;
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < 4; j++) {
			for(int k = 0; k<4; k++){
				scanf("%d", &priority[i][j][k]);
				priority[i][j][k]--;
			}
		}
	}
}

void Smell_Decrease(void) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (smell_map[i][j] > 0) {
				smell_map[i][j]--;
				if (smell_map[i][j] == 0) no_map[i][j] = 0;
			}
		}
	}
}

void Leave_Smell(void) {
	// 냄새 남기기
	int y, x;
	Smell_Decrease();
	for (int i = 1; i <= M; i++) {
		if (shark[i].l == 0) continue;
		y = shark[i].y;
		x = shark[i].x;
		no_map[y][x] = i;
		smell_map[y][x] = K;
	}
}

void Shark_Move(void) {
	int y, x, d, ny, nx, nd;
	for (int i = 1; i <= M; i++) {
		if (shark[i].l == 0) continue;
		int flag = 0;
		int y = shark[i].y;
		int x = shark[i].x;
		int d = shark[i].d;
		for (int j = 0; j < 4; j++) {
			// a. 냄새 없는 곳 우선
			nd = priority[i][d][j];
			ny = y + dy[nd];
			nx = x + dx[nd];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (smell_map[ny][nx] != 0) continue;
			flag = 1;
			shark[i].y = ny, shark[i].x = nx, shark[i].d = nd;
			break;
		}
		if (flag == 1) continue;
		for (int j = 0; j < 4; j++) {
			// b. 본인 냄새인 곳
			nd = priority[i][d][j];
			ny = y + dy[nd];
			nx = x + dx[nd];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (no_map[ny][nx] != i) continue;
			flag = 1;
			shark[i].y = ny, shark[i].x = nx, shark[i].d = nd;
			break;
		}
	}
}

void Shark_Out(void) {
	memset(map, 0, sizeof(map));
	for (int i = 1; i <= M; i++) {
		if (shark[i].l == 0) continue;
		if (map[shark[i].y][shark[i].x] != 0) {
			// 여기 있는 애랑 경쟁 -> 한 마리는 죽음
			if (map[shark[i].y][shark[i].x] < i) {
				// i가 죽음
				shark[i].l = 0;
			}
			else {
				shark[map[shark[i].y][shark[i].x]].l = 0;
				map[shark[i].y][shark[i].x] = i;
			}
			scnt--;
		}
		else {
			map[shark[i].y][shark[i].x] = i;
		}
	}
}


int main(void) {
	int t;
	Get_Input();
	for (t = 1; t <= 1000; t++) {
		Leave_Smell(); // 냄새 남기기
		Shark_Move(); // 상어들이 움직임
		Shark_Out();
		//Smell_Decrease();
		if (scnt == 1) break;
	}
	if (t > 1000) printf("-1");
	else printf("%d", t);
	return 0;
}