[BOJ-17140] 낚시왕

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

17143번: 낚시왕

 

2019년 상반기 모 기업의 코딩테스트 유사 문제입니다.

 

쉽다는 사람들이 대부분이었지만 처음 코드를 짰을때 시간초과가 많이 나서 코드를 조금 수정했는데요,

 

기존의 이동시키는 시뮬레이션 문제 같은 경우에는 한 칸씩 움직여도 시간초과가 나지 않았는데,

 

이 문제 같은 경우에는 상어가 최대 10000마리까지 있을 수 있기 때문에 시간초과가 나는것 같습니다.

 

저는 한 칸씩 이동하지 않고 재귀를 이용해 간단한 연산을 해줌으로써 시간초과가 나는 것을 줄였습니다.

 

-----------------------------------------------------------------------------------------------------------------------

 

-문제 풀이

1. 낚시왕이 낚시를 할 맵의 크기를 입력 받는다.

(낚시왕이 이동할 것을 고려해서 맵을 (1,1)부터 입력을 받았습니다.

 

2. 상어의 정보를 입력 받는다.

(입력 받은 순서대로 상어의 좌표에 해당하는 map의 위치에 상어의 인덱스 번호를 입력했습니다.)

 

3. 낚시왕이 오른쪽으로 한 칸 이동하면서 루프를 시작합니다.

(낚시왕이 입력 받은 맵의 크기까지 도달한다면 반복문 종료)

 

4. 낚시왕의 열에 있는 상어중 가장 가까운 상어를 잡습니다.

 

5. 상어를 이동시킵니다.

 

6. 이동을 한 뒤, 이동 결과에 따른 map의 정보를 다시 갱신하기 위해 map의 데이터를 -1로 초기화해줍니다.

 

7. 그 다음, 각 상어의 좌표에 해당하는 map의 위치에 상어의 정보를 업데이트해주고, 만약 그 위치에 다른 상어가 있다면 크기를 비교한 뒤 더 큰 상어를 map에 남깁니다.

 

------------------------------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

struct SHARK {
	int y, x, s, d, z;
};

struct FISHER {
	int y, x;
};
int R, C, m;
int map[101][101];
int res;
SHARK shark[10001];
FISHER fisher;

void dfs(int y, int x, int index, int dir, int speed) {

	//위
	if (dir == 1) {
		if (shark[index].y - speed == 1) {
			shark[index].y -= speed;
			shark[index].d = 2;
			return;
		}
		else if (shark[index].y - speed > 1) {
			shark[index].y -= speed;
			return;
		}
		else if (shark[index].y - speed < 1) {
			speed -= (shark[index].y - 1);
			shark[index].y -= (shark[index].y - 1);
			shark[index].d = 2;
			dfs(shark[index].y, shark[index].x, index, shark[index].d, speed);
		}
	}

	//아래
	else if (dir == 2) {
		if (shark[index].y + speed == R) {
			shark[index].y += speed;
			shark[index].d = 1;
			return;
		}
		else if (shark[index].y + speed > R) {
			speed -= (R - shark[index].y);
			shark[index].y += (R - shark[index].y);
			shark[index].d = 1;
			dfs(shark[index].y, shark[index].x, index, shark[index].d, speed);
		}
		else if (shark[index].y + speed < R) {
			shark[index].y += speed;
			return;
		}
	}

	//오른쪽
	else if (dir == 3) {
		if (shark[index].x + speed == C) {
			shark[index].x += speed;
			shark[index].d = 4;
			return;
		}
		else if (shark[index].x + speed > C) {
			speed -= (C - shark[index].x);
			shark[index].x += (C - shark[index].x);
			shark[index].d = 4;
			dfs(shark[index].y, shark[index].x, index, shark[index].d, speed);
		}
		else if (shark[index].x + speed < C) {
			shark[index].x += speed;
			return;
		}
	}

	//왼쪽
	else if (dir == 4) {
		if (shark[index].x - speed == 1) {
			shark[index].x -= speed;
			shark[index].d = 3;
			return;
		}
		else if (shark[index].x - speed > 1) {
			shark[index].x -= speed;
			return;
		}
		else if (shark[index].x - speed < 1) {
			speed -= (shark[index].x - 1);
			shark[index].x -= (shark[index].x - 1);
			shark[index].d = 3;
			dfs(shark[index].y, shark[index].x, index, shark[index].d, speed);
		}
	}
}

int main(void) {

	scanf("%d %d %d", &R, &C, &m);

	for (int y = 1; y <= R; y++) {
		for (int x = 1; x <= C; x++) {
			map[y][x] = -1;
		}
	}

	for (int i = 0; i < m; i++) {
		scanf("%d %d %d %d %d", &shark[i].y, &shark[i].x, &shark[i].s, &shark[i].d, &shark[i].z);
		map[shark[i].y][shark[i].x] = i;
	}

	fisher.y = 0, fisher.x = 0;

	while (1) {

		fisher.x += 1;
		if (fisher.x > C) break;

		//낚시왕의 열에 있는 상어 중, 제일 가까운 상어를 잡는다
		int temp = 0;
		bool flag = false;

		for (int y = 1; y <= R; y++) {
			if (map[y][fisher.x] != -1) {
				temp = map[y][fisher.x];
				flag = true;
				break;
			}
		}

		if (flag) {
			res += shark[temp].z;
			map[shark[temp].y][shark[temp].x] = -1;
			shark[temp].y = 0, shark[temp].x = 0, shark[temp].s = 0, shark[temp].d = 0, shark[temp].z = 0;
		}

		//상어 이동
		for (int i = 0; i < m; i++) {
			int speed = shark[i].s;
			
			if (speed == 0) continue;

			dfs(shark[i].y, shark[i].x, i, shark[i].d, speed);

		}

		for (int y = 1; y <= R; y++) {
			for (int x = 1; x <= C; x++) {
				map[y][x] = -1;
			}
		}

		//상어 먹기
		for (int i = 0; i < m; i++) {
			if (map[shark[i].y][shark[i].x] != -1) {
				int index = map[shark[i].y][shark[i].x];
		
				if (shark[i].y == shark[index].y && shark[i].x == shark[index].x) {
					if (shark[i].z > shark[index].z) {
						map[shark[i].y][shark[i].x] = i;
						shark[index].y = 0, shark[index].x = 0, shark[index].s = 0, shark[index].d = 0, shark[index].z = 0;
					}
					else {
						map[shark[index].y][shark[index].x] = index;
						shark[i].y = 0, shark[i].x = 0, shark[i].s = 0, shark[i].d = 0, shark[i].z = 0;
					}
				}
			}
			else {
				map[shark[i].y][shark[i].x] = i;
			}
		}

		
	}
	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}