백준 알고리즘 16236_아기상어 C

문제

(링크)16236번: 아기 상어 (acmicpc.net)

16236번: 아기 상어

 

사고과정

문제를 풀때 어떻게 접근할까 생각을하는데 조금 애먹은 문제다. <가장 가까운 물고기> 중 <좌상단>에 위치한 물고기를 먼저 먹으라는 조건이 있기 때문이다.

먼저, 최단 거리를 우선으로 찾으려면 bfs를 사용하는 것이 좋다. 현재 상어의 위치로부터 거리순으로 탐색할 수 있기 떄문이다. 대신 같은 거리에 존재하는 물고기가 여러마리면 위/왼쪽 방향의 물고기를 먼저 먹는다고 했으니 그 부분도 고려해줘야 한다. 

최대한 피요없는 탐색을 줄이기 위해 <현재 먹을 수 있는 물고기의 거리>보다 멀리 있는 좌표를 만나면 탐색을 멈췄다. 이후 먹을 수 있는 물고기의 좌표를 비교하여 조건에 부합하는 물고기를 택하려 했다. 이 방법을 사용할 때 조금 꼬여, 같은 거리에 있는 먹을 수 있는 물고기들을 모두 저장하여 비교하는 식으로 풀이했다.  

 

내코드

#include <stdio.h>
#include <stdlib.h>


typedef struct {
	int x, y, distance;
}queue;

int N;
queue Q[400];
int front, rear;

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

void clear_matrix(int** visit) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = 0;
		}
	}
}

void init_queue() {
	rear = 0;
	front = 0;
}

void getFish(queue* temp, int T, int* x, int* y) {
	int min_y = 23, count_y = 0;
	int index[500];
	for (int i = 0; i < T; i++) {
		if (min_y > temp[i].y) {
			min_y = temp[i].y;
			count_y = 0;
			index[count_y++] = i;
		}
		else if (min_y == temp[i].y) {
			index[count_y++] = i;
		}
	}
	int min_x = temp[index[0]].x;
	if (count_y > 1) {
		for (int i = 1; i < count_y; i++) {
			int ind = index[i];
			if (min_x > temp[ind].x) {
				min_x = temp[ind].x;
			}
		}
	}
	*x = min_x;
	*y = min_y;
}
int SearchFish(int** map,int** visit,int* time,int shark) {
	int eatFlag = 0,temp_distance=100000;
	queue temp[1000];
	int count_temp=0;
	while (front < rear) {
		int popX = Q[front].x;
		int popY = Q[front].y;
		int popD = Q[front].distance;
		front++;
		if (popD >= temp_distance)break;//물고기를 먹을 수 있는 상태에서 같은거리의 위치조사를 마치면 끝

		for (int i = 0; i < 4; i++) {
			int X = popX + dx[i];
			int Y = popY + dy[i];
			
			if (X >= 0 && X < N && Y >= 0 && Y < N) {
				if (visit[Y][X] == 0 && map[Y][X] <= shark) {
					if (map[Y][X] == 0 || map[Y][X] == shark) {
						Q[rear].y = Y;
						Q[rear].x = X;
						Q[rear].distance = popD + 1;
						visit[Y][X] = 1;
						rear++;
					}
					else {
						eatFlag = 1; //먹을 수 있는 애가 있으면 그 이후의 고기는 생각안함,
						visit[Y][X] = 1;
						temp[count_temp].y = Y;	//대신 같은거리에 있는 고기들끼리 좌표비교 해줄거임
						temp[count_temp].x = X;
						count_temp++;
						temp_distance = popD + 1;
					}
				}
			}

		}
	}
	clear_matrix(visit); //visit초기화
	if (eatFlag) {
		*time += temp_distance;
		init_queue();
		int tx, ty;
		getFish(temp,count_temp, &tx, &ty);

		map[ty][tx] = 0;
		Q[rear].y = ty;
		Q[rear].x = tx;
		Q[rear].distance = 0;
		rear++;
		visit[ty][tx] = 1;
	}

	return eatFlag;
}


int main() {
	int i,j;
	scanf("%d", &N);
	int** map = (int**)malloc(N * sizeof(int*));
	int** visit = (int**)calloc(N , sizeof(int*));
	for (i = 0; i < N; i++) {
		map[i] = (int*)malloc(N * sizeof(int));
		visit[i] = (int*)calloc(N , sizeof(int));
	}

	front = 0;
	rear = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) {
				Q[rear].x = j;
				Q[rear].y = i;
				Q[rear].distance = 0;
				rear++;
				visit[i][j] = 1;
				map[i][j] = 0;
			}
		}
	}

	int shark_size = 2,time=0,eat=0;
	while (SearchFish(map,visit,&time,shark_size)) {
		eat++;
		if (eat == shark_size) {
			shark_size++;
			eat = 0;
		}
	}

	printf("%d", time);


	for (i = 0; i < N; i++) {
		free(map[i]);
		free(visit[i]);
	}
	free(map);
	free(visit);
	return 0;
}

먼저 main함수 내에서 <물고기를 먹을 수 있는 동안> eat과 shar_size변수를 통하여 매 과정 갱신되는 정보를 바꿔주었다.  SearchFish함수는 말 그대로 물고기를 찾아주는 역할을 한다. 현재 상어 위치를 시작으로 주변을 탐색하는데, 빈공간이거나 상어와 물고기의 크기가 같은 곳은 queue에 넣어주고 먹을 수 있는 물고기는 temp배열에 index를 저장해준다. 이후 temp_distance를 이용하여 거리 조건을 이용해 탐색 횟수를 줄여준다.

만약 queue가 비면 flag를 이용해 getFish함수를 실행시킬지 결정한다. 이후 다음 차례에 사용하기 위해 queue를 비워준다. getFish함수는 같은 거리에 있는 물고기들을 저장해준 배열에서 문제 조건에 부합하는 좌표를 구하는 함수이다.

 

피드백

잘만 조건을 추가하면 중간에 getFish함수를 사용하지 않아도 될 것 같다. 조금 더 생각해 볼 것.