백준 17143 - 낚시왕

문제링크

• 백준 17143

문제설명

• RxC 크기의 격자판에서 상어낚시를 한다.
• 낚시왕은 0번 열에 서있다가 1초동안 다음과 같은 로직을 수행한다.
  • 낚시왕이 오른쪽으로 한 칸 이동한다.
  • 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
  • 상어가 이동한다.
• 상어의 이동 로직은 다음과 같다.
  • 상어는 크기와 속도(방향, 속력)를 가진다. (칸 수/sec)
  • 1초마다 상어는 방향에 따라 속력만큼 칸을 이동해야 하는데, 벽에 닿는 경우 방향을 반대로 바꿔서 이동한다.
  • 상어가 이동을 마친 후에 한 칸에 두 마리 이상의 상어가 있는 경우 크기가 큰 상어가 다른 상어를 모두 잡아먹는다.
• C열까지 낚시왕이 낚시를 했을 때 잡은 상어 크기의 합을 구하라

문제접근

• 상어의 정보를 담는 구조체를 선언한다.
  • 상어의 좌표정보, 속력, 방향, 크기, 상태(격자판에 남아 있는지)
• 낚시왕이 상어를 잡는다.
  • 상어를 x좌표 정보를 기준으로 오름차순 정렬한다.
  • 낚시왕과 같은 열에 위치하는 상어를 찾고 status=false 로 바꾼다.
• 상어를 이동시킨다.
  • 상어가 처음 방향, 처음 위치에 돌아오는 주기를 계산한다. 횡방향으로 이동하는 경우 (C-1)x2 칸이 주기가 되고, 종방향으로 이동하는 경우 (R-1)x2 칸이 주기가 된다.
  • 상어의 속력을 주기로 나누었을 때 나머지만큼 상어를 이동시킨다. 이때 양 벽에 닿는 경우 방향을 바꾸고 칸을 이동한다.
• 같은 칸에 위치하는 상어들 중 크기가 가장 큰 상어만 남긴다.
  • 상어를 크기 순서대로 내림차순 정렬한다.
  • 격자판을 나타내는 2차원 배열 board 에 위치에 따른 상어의 유무를 표시하고, 먼저 해당 위치에 들어가는 상어가 그 칸에서 가장 크기가 큰 상어가 된다.
  • 이미 존재하는 칸에 상어가 들어가게 된다면 해당 상어의 status=false 로 바꾼다.
• 위 3가지 과정을 1번~C번 열까지 반복한다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
using namespace std;

typedef struct _shark {
	int xpos, ypos, speed, size, dir;
	bool status;
} Shark; 
int R, C, M;
int ans = 0;
int board[101][101] = { 0, };
vector<Shark> sharkList;

// 땅에 가까운 순서대로 정렬
bool cmpRow(Shark s1, Shark s2) {
	return s1.xpos < s2.xpos;
}

void catchShark(int idx) {
	sort(sharkList.begin(), sharkList.end(), cmpRow);
	for (int i = 0; i < sharkList.size(); i++) {
		if (sharkList[i].status == false) continue;
		if (sharkList[i].ypos == idx) {
			ans += sharkList[i].size;
			sharkList[i].status = false;
			break;
		}
	}
}

void moveShark() {
	int vPeriod = (R - 1) * 2;
	int hPeriod = (C - 1) * 2;
	
	for (int i = 0; i < sharkList.size(); i++) {
		if (sharkList[i].status == false) continue;
		int dir = sharkList[i].dir;
		int remainSpeedV = sharkList[i].speed % vPeriod;
		int remainSpeedH = sharkList[i].speed % hPeriod;
		int xpos = sharkList[i].xpos;
		int ypos = sharkList[i].ypos;
		if (dir == 1 || dir == 2) {
			for (int i = 0; i < remainSpeedV; i++) {
				if (dir == 1) {
					xpos--;
					if (xpos == 0) {
						dir = 2;
						xpos = 2;
						continue;
					}
				}
				else if (dir == 2) {
					xpos++;
					if (xpos > R) {
						dir = 1;
						xpos = R - 1;
					}
				}
			}
		}
		else if (dir == 3 || dir == 4) {
			for (int i = 0; i < remainSpeedH; i++) {
				if (dir == 4) {
					ypos--;
					if (ypos == 0) {
						dir = 3;
						ypos = 2;
						continue;
					}
				}
				else if (dir == 3) {
					ypos++;
					if (ypos > C) {
						dir = 4;
						ypos = C - 1;
					}
				}
			}
		}
		sharkList[i].xpos = xpos;
		sharkList[i].ypos = ypos;
		sharkList[i].dir = dir;
	}
}

// 크기가 큰 순서대로 정렬
bool cmpSize(Shark s1, Shark s2) {
	return s1.size > s2.size;
}

void setLiveShark() {
	memset(board, 0, sizeof(board));
	sort(sharkList.begin(), sharkList.end(), cmpSize);
	for (int i = 0; i < sharkList.size(); i++) {
		if (sharkList[i].status == false) continue;
		if (board[sharkList[i].xpos][sharkList[i].ypos] == 0)
			board[sharkList[i].xpos][sharkList[i].ypos] = 1;
		else if (board[sharkList[i].xpos][sharkList[i].ypos] == 1)
			sharkList[i].status = false;
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d %d", &R, &C, &M);

	Shark s;
	for (int i = 0; i < M; i++) {
		scanf("%d %d %d %d %d", &s.xpos, &s.ypos, &s.speed, &s.dir, &s.size);
		s.status = true;
		sharkList.push_back(s);
	}
	
	for (int idx = 1; idx <= C; idx++) {
		catchShark(idx);
		moveShark();
		setLiveShark();
	}

	printf("%d\n", ans);
	return 0;
}