백준 알고리즘 17143_낚시왕 C

문제

(링크)17143번: 낚시왕 (acmicpc.net)

17143번: 낚시왕

사고과정

처음 문제를 접할 땐 문제를 푸는 방법 자체는 그리 어렵지 않을 거라 생각했다. 하지만 상어의 정보를 어떤식으로 저장하느냐가 관건이었다. 그래서 나는 map에 상어의 이름을 저장하고, 그 상어의 이름을 index로 하는 구조체 배열에 상어의 정보를 저장했다. 이렇게 하면 map을 전체 탐색하지 않고 상어의 개수만큼만 탐색할 수 있기 때문이고, 필요없는 메모리 사용을 줄일 수 있을 거라 생각했다,

 

내코드

#include <stdio.h>
#include <stdlib.h>
//시관초과

typedef struct {
	int x, y, dir, size, vel;
}shark;

int height, width,shark_num,answer;
int dx[4] = { 0,0,1,-1 };//up0 down1 right2 left3
int dy[4] = { -1,1,0,0 };

int name(int i) {//index to name(shark)
	return i + 1;
}
int name2ind(int i) {
	return i - 1;
}

void getShark(int** map, int fisher,shark* s) {
	for (int i = 0; i < height; i++) {
		if (map[i][fisher] != 0) {
			int t = name2ind(map[i][fisher]);
			answer += s[t].size;
			s[t].size = 0;
			map[i][fisher] = 0;
			return;
		}
	}
}
/*
void goStraight(int* x, int* y, int count, int vel, int* dir) {
	if (count == vel) {
		return;
	}

	int X = *x + dx[*dir];
	int Y = *y + dy[*dir];
	if (X >= 0 && X < width && Y >= 0 && Y < height) {
		*x = X;
		*y = Y;
	}
	else {
		if (*dir == 0)*dir = 1;
		else if (*dir == 1)*dir = 0;
		else if (*dir == 2)*dir = 3;
		else if (*dir == 3)*dir = 2;
		

		*x = *x + dx[*dir];
		*y = *y + dy[*dir];
	}

	goStraight(x, y, count + 1, vel, dir);
}
*/ 
//이 함수를 이용하면 재귀적으로 탐색을 하여 직관적으로 쉽게 새 좌표를 구할 수 있지만, 시간이 초과된다.

void goStraight(int* x,int* y,int vel,int* dir) {
	if (*dir == 0) {
		if (*y - vel >= 0) {
			*y -= vel;
		}
		else {
			vel -= *y;//y=0
			if ((vel / (height-1)) % 2 == 0) {
				*dir = 1;
				*y = (vel % (height-1));
			}
			else {
				*y = (height-1) - (vel % (height-1));
			}
		}
	}
	else if (*dir == 1) {
		if (*y + vel < height) {
			*y += vel;
		}
		else {
			vel -= (height - *y-1);
			if ((vel / (height - 1)) % 2 == 0) {
				*dir = 0;
				*y = height-1 -(vel % (height - 1));
			}
			else {
				*y = (vel % (height - 1));
			}
		}
	}
	else if (*dir == 2) {
		if (*x + vel < width) {
			*x += vel;
		}
		else {
			vel -= (width - 1 - *x);
			if ((vel / (width - 1)) % 2 == 0) {
				*dir = 3;
				*x = width - 1-(vel % (width - 1));
			}
			else {
				*x = (vel % (width - 1));
			}
		}
	}
	else if (*dir == 3) {
		if (*x - vel >= 0) {
			*x -= vel;
		}
		else {
			vel -= *x;
			if ((vel / (width - 1)) % 2 == 0) {
				*dir = 2;
				*x = (vel % (width - 1));
			}
			else {
				*x = width - 1 - (vel % (width - 1));
			}
		}
	}


}
void moveShark(int** map, shark* s) {
	int** temp = (int**)calloc(height , sizeof(int*));
	for (int i = 0; i < height; i++) {
		temp[i] = (int*)calloc(width, sizeof(int));
	}

	for (int i = 0; i < shark_num; i++) {
		if (s[i].size > 0) {//unless shark is caught
			int x = s[i].x, y = s[i].y, dir = s[i].dir, vel = s[i].vel, size = s[i].size;
			map[y][x] = 0;
			//goStraight(&x, &y, 0, vel, &dir);
			goStraight(&x, &y, vel, &dir);
			if (temp[y][x] != 0) {
				int O = name2ind(temp[y][x]);
				if (s[O].size > size) {//먼저 움직인 상어가 더 크면 스킵
					s[i].size = 0;
					continue;
				}
				else {//새로 들어온 상어가 더 크면 바꿔줌(먹힘)
					s[O].size = 0;
					s[i].x = x;
					s[i].y = y;
					s[i].dir = dir;
					temp[y][x] = name(i);
				}
			}
			else if (temp[y][x]==0) {
				temp[y][x] = name(i);
				s[i].x = x;
				s[i].y = y;
				s[i].dir = dir;
			}
		}
	}

	for (int i = 0; i < shark_num; i++) {
		if (s[i].size > 0) {
			int x = s[i].x;
			int y = s[i].y;
			map[y][x] = temp[y][x];
		}

	}
	for (int i = 0; i < height; i++) {
		free(temp[i]);
	}
	free(temp);
}


int main() {
	int i, j;
	scanf_s("%d %d %d", &height, &width, &shark_num);
	int** map = (int**)calloc(height , sizeof(int*));
	for (i = 0; i < height; i++) {
		map[i] = (int*)calloc(width , sizeof(int));
	}
	shark* S = (shark*)malloc(shark_num * sizeof(shark));

	for (i = 0; i < shark_num; i++) {
		int y, x, vel, dir, size;
		scanf_s("%d %d %d %d %d", &y, &x, &vel, &dir, &size);
		S[i].y = y - 1;
		S[i].x = x - 1;
		S[i].vel = vel;
		S[i].dir = dir-1;
		S[i].size = size;
		map[y - 1][x - 1] = name(i);
	}

	answer = 0;
	for (int fisher = 0; fisher < width; fisher++) {
		getShark(map, fisher, S);
		moveShark(map, S);
	}
	printf("%d", answer);




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

코드는 생각보다 간단하다. 주의해줘야 할점은 map에 들어가는 x,y좌표와 dir은 문제에서 주어지는 것보다 1작다는 것. 이 부분만 유의하면 에러가 날 가능성은 거의 없다. 

먼저 fisher가 0부터 map의 가로길이만큼 움직인다. 움직이는 동안 낚시꾼이 있는 열의 상어를 찾아준다. 이때 상어를 한마리 찾는 순간 함수를 종료시켜 추가적인 탐색을 하지 않도록 한다.

이후 상어들이 움직여야 하는데, 중요한 것은 상어들이 동시에 움직이는데 코드상에선 순서대로 움직이므로, map에서 직접 비교를 해주면 <아직 움직이지 않은 상어>와 크기를 비교할 수도 있게 된다. 그러므로 temp배열을 이용하여 map을 갱신하도록 한다. 상어가 이동할 땐 상어가 있는(size가 0이 되지 않은, size가 0인 상어는 먹힌 상어이거나 잡힌상어) 칸에서 goStraight함수를 이용하여 새로운 좌표를 구해준다. (goStraight함수는 단순히 새 좌표를 구하는 함수) 이후 같은 좌표의 temp 배열에 <이미 이동을 한 상어>가 있다면 size를 비교하여 정보를 갱신한다. 

피드백

처음 문제를 풀 땐시간초과가 생겼다. 사실 코드를 짜면서 상어가 이동하는 부분을 너무 날로 먹는다는 것을 인지했지만 함수를 다시 만들기 너무 귀찮았다. 또한 shark 구조체 배열에서 먹힌 상어를 제거해주지 않고 탐색에서 계속 사용하기 때문에 시간이 늘어났다. 이 부분만 잘 만져주면 메모리와 시간을 더 줄일 수 있을 것 같다.