[BOJ] #17143 _ 낚시왕

[낚시왕] https://www.acmicpc.net/problem/17143

17143번: 낚시왕

본 문제는 상어를 이동하고,

이동 후 상어의 위치 및 큰 상어가 작은 상어를 먹는 것을 구현하는 것이 문제이다.

 

해당 문제는 다음과 같은 단계 별로 구현하면 된다.

 

1. 낚시왕 이동
2. 가장 가까운 상어 잡기
3. 상어 이동
4. 이동 후 상어를 좌표에 맞게 맵에 위치 시킴

 

상어를 이동시킬 때, 한 칸씩 이동하면 시간 초과가 발생한다.

따라서, 상어를 한번에 양 끝점으로 보내는 방법으로 구현하였다.

 

상어를 모두 이동시키고 난 후에 맵에 상어를 뿌려준다.

이때, 상어의 크기를 비교해 뿌려준다.

 

[ 소스 코드 ]

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX 101

using namespace std;

typedef struct shark {
	int s, d, z;
}Shark;

int dx[] = { 0, 0, 0, 1, -1 }, dy[] = { 0, -1, 1, 0, 0 };
int R, C, M, map[MAX][MAX];
vector<Shark> shark_info;

int fishShark(int c);
void moveShark();
int main() {
	scanf("%d %d %d", &R, &C, &M);

	Shark tmp;
	shark_info.push_back(tmp);
	for(int i=1; i<=M; i++) {
		int r, c;
		scanf("%d %d %d %d %d", &r, &c, &tmp.s, &tmp.d, &tmp.z);
		map[r][c] = i;
		shark_info.push_back(tmp);
	}

	int result = 0;
	for (int i = 1; i <= C; i++) {
		if (M <= 0) break;
		result += fishShark(i);
		moveShark();
	}

	printf("%d\n", result);

	return 0;
}

int fishShark(int c) {
	int shark_size = 0;
	for (int i = 1; i <= R; i++) {
		if (map[i][c] > 0) {
			shark_size = shark_info[map[i][c]].z;
			map[i][c] = 0;
			M--;
			break;
		}
	}

	return shark_size;
}

void moveShark() {
	int tmp[MAX][MAX] = { 0, };

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (map[i][j] == 0) continue;

			int tmp_r = i, tmp_c = j, tmp_s = shark_info[map[i][j]].s;
			while (tmp_s > 0) {
				if (tmp_r + tmp_s * dy[shark_info[map[i][j]].d] < 1) {
					tmp_s -= (tmp_r - 1);
					tmp_r = 1;
					shark_info[map[i][j]].d = 2;
				}
				else if (tmp_r + tmp_s * dy[shark_info[map[i][j]].d] > R) {
					tmp_s -= (R - tmp_r);
					tmp_r = R;
					shark_info[map[i][j]].d = 1;
				}
				else if (tmp_c + tmp_s * dx[shark_info[map[i][j]].d] < 1) {
					tmp_s -= (tmp_c - 1);
					tmp_c = 1;
					shark_info[map[i][j]].d = 3;
				}
				else if (tmp_c + tmp_s * dx[shark_info[map[i][j]].d] > C) {
					tmp_s -= (C - tmp_c);
					tmp_c = C;
					shark_info[map[i][j]].d = 4;
				}
				else {
					tmp_r += (tmp_s * dy[shark_info[map[i][j]].d]);
					tmp_c += (tmp_s * dx[shark_info[map[i][j]].d]);
					tmp_s = 0;
				}

			}
			
			if (tmp[tmp_r][tmp_c] > 0) {
				if (shark_info[tmp[tmp_r][tmp_c]].z < shark_info[map[i][j]].z) {
					tmp[tmp_r][tmp_c] = map[i][j];
				}
			}
			else tmp[tmp_r][tmp_c] = map[i][j];
		}
	}

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			map[i][j] = tmp[i][j];
		}
	}
}