[BOJ] 17143 낚시왕

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

Note

낚시왕이 낚시를 하며 잡은 상어 크기의 총합을 출력해주자.

시뮬레이션의 정석이라는 생각이 든 문제.
낚시왕은 1부터 가로의 끝까지 천천히 한칸씩 움직인다.
상어는 바라보고 있는 방향으로 자신의 속도만큼 움직인다. 벽에 부딪히는 상황이 오면 상어는 방향을 바꿔 남은 거리만큼 움직인다.
가장 까다로웠던게 마지막 조건이었다.
한 칸에 여러 상어가 있을 수 있고, 그 경우에는 가장 큰 상어가 나머지 상어를 잡아먹는다. 상어의 크기에는 변함이 없다.
낚시왕은 낚시에 성공 할 수도 있지만, 잡지 못하는 경우도 있다.
낚시왕이 움직여 낚시를 한 후, 상어가 움직인다. 모든 상어는 동시에 움직인다.

직관적이고 간단한 문제지만 생각보다 상어의 움직임을 구현하는데 시간이 오래 걸렸다. 통과는 했지만 해당 부분이 생각보다 너무 어리숙하게 구현됬다.

알고리즘

1. 상어의 위치정보를 입력받는다.
2. 낚시왕이 낚시를 한다. 잡을 수 있는 경우 가장 위쪽의 상어를 잡고, 합을 저장한다.
3. 상어를 움직인다. 3-1. x축, y축으로의 이동 거리를 구한다.
   1. x축, y축으로 이동할 거리가 존재 한다면 바라보고 있는 방향으로 이동한다.
   2. 이동하는 거리가 벽에 닿지 않는다면 남은 거리만큼 움직인다.
   3. 이동하는 거리가 벽까지 거리보다 멀다면 벽 까지 이동하고 방향을 반대 방향으로 바꾼다.
   4. x축, y축으로 이동할 거리가 0일 때 까지 반복한다.
4. 잡아먹히는 상어를 계산한다. 잡아먹힌 상어는 죽은 상어로 판단한다.
5. 낚시왕이 끝까지 갈 때 까지 반복한다.
6. 총 합을 출력한다.

소스코드

#include <iostream>
#include <vector>

using namespace std;

const short MAX = 100;

const short posX[4] = { 0, 0, 1, 1 }; // N S E W
const short posY[4] = { 1, 1, 0, 0 };

int row, col, sharkCount;

struct Point {
	short x;
	short y;
	short speed;
	short direction;
	short size;
};

vector<Point> sharks;
vector<bool> deadSharks;

void updateShark() {

	for (int i = 0; i < sharkCount; i++)
	{
		if (deadSharks[i])
			continue;

		Point cur = sharks[i];

		int xMove = posX[cur.direction - 1] * cur.speed;
		int yMove = posY[cur.direction - 1] * cur.speed;

		while (xMove) {
			int moveDistace;
			if (cur.direction == 3)
			{
				if (cur.x + xMove < row)
				{
					cur.x += xMove;
					moveDistace = xMove;
				}
				else
				{
					moveDistace = row - cur.x;
					cur.x = row;
					cur.direction = 4;
				}
			}
			else if (cur.direction == 4)
			{
				if (cur.x - xMove > 0)
				{
					cur.x -= xMove;
					moveDistace = xMove;
				}
				else
				{
					moveDistace = cur.x - 1;
					cur.x = 1;
					cur.direction = 3;
				}

			}
			xMove -= moveDistace;
		}

		while (yMove) {
			int moveDistace;
			if (cur.direction == 1)
			{
				if (cur.y - yMove > 0)
				{
					cur.y -= yMove;
					moveDistace = yMove;
				}
				else
				{
					moveDistace = cur.y - 1;
					cur.y = 1;
					cur.direction = 2;
				}
			}
			else if (cur.direction == 2)
			{
				if (cur.y + yMove < col)
				{
					cur.y += yMove;
					moveDistace = yMove;
				}
				else
				{
					moveDistace = col - cur.y;
					cur.y = col;
					cur.direction = 1;
				}
			}

			yMove -= moveDistace;
		}

		sharks[i] = cur;
	}

	for (int i = 0; i < sharkCount; i++)
	{
		if (deadSharks[i])
			continue;

		for (int j = i + 1; j < sharkCount; j++)
		{
			if (deadSharks[j])
				continue;

			if (sharks[i].x == sharks[j].x && sharks[i].y == sharks[j].y) {
				if (sharks[i].size < sharks[j].size)
					deadSharks[i] = true;
				else if (sharks[i].size > sharks[j].size)
					deadSharks[j] = true;
			}
		}
	}
}

int topShark(int pos) {

	int idx = -1;

	for (int i = 0; i < sharkCount; i++) {
		if (deadSharks[i] || sharks[i].x != pos)
			continue;

		if (idx == -1)
			idx = i;
		else if (sharks[idx].y > sharks[i].y)
			idx = i;
	}

	return idx;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int res = 0;

	cin >> col >> row >> sharkCount;

	sharks.resize(sharkCount);
	deadSharks.resize(sharkCount);

	for (int i = 0; i < sharkCount; i++)
		cin >> sharks[i].y >> sharks[i].x >> sharks[i].speed >> sharks[i].direction >> sharks[i].size;

	for (int i = 0; i < row; i++)
	{
		int top = topShark(i + 1);

		if (top != -1) {
			//cout << i + 1 << " : " << sharks[top].size << '\n';

			res += sharks[top].size;
			deadSharks[top] = true;
		}

		updateShark();
	}

	cout << res;

	return 0;
}

2019-04-18 01:56:11에 Tistory에서 작성되었습니다.