[백준 17143] 낚시왕 (C++)

문제 링크: www.acmicpc.net/problem/17143

17143번: 낚시왕

1. 주의할 점

- 상어가 격자판의 끝에 도달할 경우, 방향을 바꿔서 전진하는 과정 구현

- 상어에 대한 정보의 표현 방법(배열 or 벡터 등등)

 

2. 구현

- 상어에 대한 정보를 입력받을 때 방향의 경우, 따로 설정한 방향으로 변환한다(0~3: 상우하좌 순서). 방향값 변환 이후, Shark 벡터에 상어에 대한 정보를 저장한다

- Player 변수를 통해 현재 낚시왕의 위치를 표시한다

- checkDown() 함수를 통해 현재 낚시왕의 아래에 물고기가 있다면, 가장 위에 있는 물고기의 크기만큼 Result에 더하고 해당 물고기를 사망처리한다

- sharkMv() 함수의 초기에 Arr[][] 배열을 전부 -1로 초기화하여 모든 상어의 이동후 중복 여부를 체크한다

- 상어가 현재 방향으로 진행하는 거리: dx[cd]*cs 와 dy[cd]*cs다. 이때, cs의 값이 Row나 Col에 비해 매우 클 수 있기 때문에, 1회 왕복 거리인 2*(Col-1) 와 2*(Row-1)로 나눈 나머지만큼 추가 이동한다고 한다(사소한 시간 단축 차이)

- 현재 위치에서 추가 이동거리만큼 이동했을 때의 위치를 ny, nx에 저장하고 ny,nx가 격자판의 범위 밖에 있다면 While()문을 통해 위치와 진행방향을 수정한다(While문이 중요!)

- 이동한 위치의 Arr[][] 값을 통해 상어의 유무를 판단하고 이미 상어가 존재하지 않으면 이동을, 이미 상어가 존재한다면 크기를 비교해서 큰 상어 생존 + 작은 상어 사망처리를 수행한다

 

#include <iostream>
#include <vector>
using namespace std;
struct info {
	int y, x, s, dir, val;
	bool dead = false;
};
info tmp;
int arr[101][101];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int result = 0, player = 0, row, col, num, x, y, val, s, dir;
vector<info> shark;

void checkDown() {
	int idx = -1, height = row + 1;
	for (int i = 0; i < shark.size(); i++) {
		if (shark[i].dead) continue;
		int sy = shark[i].y;
		int sx = shark[i].x;
		if (player == sx && sy < height) {
			height = sy;
			idx = i;
		}
	}
	if (idx != -1) {		//잡은 경우
		result += shark[idx].val;
		shark[idx].dead = true;
	}
}

void sharkMv() {
	for (int i = 1; i <= row; i++)
		for (int j = 1; j <= col; j++)
			arr[i][j] = -1;
	for (int i = 0; i < shark.size(); i++) {
		if (shark[i].dead) continue;
		int cx = shark[i].x;
		int cy = shark[i].y;
		int cs = shark[i].s;
		int cd = shark[i].dir;
		int cv = shark[i].val;
		int nd = cd;
		int nx = cx + (dx[cd] * cs) % (2 * (col - 1));
		int ny = cy + (dy[cd] * cs) % (2 * (row - 1));
		while (nx < 1 || nx > col) {
			if (nx < 1) {
				nx = 2 - nx;
				nd = (nd + 2) % 4;
			}
			if (nx > col) {
				nx = 2 * col - nx;
				nd = (nd + 2) % 4;
			}
		}
		while (ny < 1 || ny > row) {
			if (ny < 1) {
				ny = 2 - ny;
				nd = (nd + 2) % 4;
			}
			if (ny > row) {
				ny = 2 * row - ny;
				nd = (nd + 2) % 4;
			}
		}
		val = arr[ny][nx];
		if (val == -1) {		//해당 자리에 아무 상어도 없는 경우
			arr[ny][nx] = i;
			shark[i].x = nx;
			shark[i].y = ny;
			shark[i].dir = nd;
		}
		else {		//해당 자리에 다른 상어가 있는 경우
			if (shark[val].val > cv)    shark[i].dead = true;
			else {
				arr[ny][nx] = i;
				shark[val].dead = true;
				shark[i].x = nx;
				shark[i].y = ny;
				shark[i].dir = nd;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col >> num;
	for (int i = 0; i < num; i++) {
		cin >> y >> x >> s >> dir >> val;
		if (dir == 1) dir = 0;
		else if (dir == 3) dir = 1;
		else if (dir == 4) dir = 3;
		shark.push_back({ y,x,s,dir,val });
	}
	while (player <= col) {
		player++;
		checkDown();
		sharkMv();
	}
	cout << result;
	return 0;
}