[백준][C++] 17143: 낚시왕

문제

17143번: 낚시왕

풀이

구현, 시뮬레이션

 

• vector<Shark>(sharks)에 상어를 입력받는다. 
• 보드 배열(board)의 각 칸에는 현재 위치한 상어의 index가 입력된다. 상어가 위치해 있지 않은 경우 -1이 기본값으로 설정된다. 
• 다음 보드(next_board)의 상태를 나타내는 배열을 만든다. 마찬가지로 기본값은 -1로 설정된다. 
• 다음의 작업이 C번 실행된다. 
  • 낚시왕이 위치한 열에 있는 상어 중에서 행이 0과 가장 가까운 상어를 잡는다.
  • 남아 있는 상어의 위치를 이동하여 next_board에 해당 상어의 index입력한다. 
    • 만약 입력한 위치에 이미 상어가 위치해 있다면 크기를 비교해서 index를 수정하고 먹힌 상어는 없앤다. 
  • next_board의 값을 board에 복사한다. 

 

위의 작업에서 상어를 이동시킬 때, 상어의 속도(speed)만큼 반복문을 돌려서 처리하면 시간 초과가 발생한다. speed에 mod 연산을 해서 speed를 줄인다면 시간 초과가 발생하지 않는다. 

현재 상어가 1번에 위치하고 속도가 8이라면, 이동 후에는 3번 에 위치하게 된다. 이는 속도가 2인 경우에도 동일하다. 각 줄의 마지막 칸은 다음 줄의 첫번째 칸과 연결되어 있기 때문에 다음의 연산으로 speed를 줄일 수 있다. 

speed = speed % ((C - 1) × 2)

 

추가로, speed 만큼 반복문을 돌려 상어의 위치를 이동시키지 않고, speed와 상어의 방향에 맞게 상어를 이동시키고 범위에 맞게 조정한다면 시간을 더 줄일 수 있다. 

 

코드

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

struct Shark
{
	int pos_x = -1;
	int pos_y = -1;
	int speed = -1;
	int dir = -1;
	int size = -1;
	bool alive = true;
};

int R, C, M;
int board[102][102];
int next_board[102][102];
vector<Shark> sharks;
int answer = 0;

int move_x[4] = { -1, 1, 0, 0 };
int move_y[4] = { 0, 0, 1, -1 };

void fishing(int person)
{
	// 현재 열에서 행이 0과 가장 가까운 위치의 상어를 잡는다.
	for (int x = 0; x < R; ++x)
	{
		if (board[x][person] != -1)
		{
			Shark* shark = &sharks[board[x][person]];
			answer += shark->size;

			board[x][person] = -1;

			shark->alive = false;

			break;
		}
	}
}

void move_sharks()
{
	for (int idx = 0; idx < sharks.size(); ++idx)
	{
		Shark* shark = &sharks[idx];

		if (shark->alive == false)
		{
			continue;
		}

		int next_x = shark->pos_x;
		int next_y = shark->pos_y;
		int speed = shark->speed;

		// 세로로 움직이는 경우
		if (shark->dir < 2)
		{
			speed %= ((R - 1) * 2);

			next_x += speed * move_x[shark->dir];

			// 움직인 다음 범위를 초과한 경우 조정
			if (next_x >= R)
			{
				next_x = (2 * R) - 2 - next_x;
				shark->dir = 0;

				if (next_x < 0)
				{
					next_x *= -1;
					shark->dir = 1;
				}
			}
			else if (next_x < 0)
			{
				next_x *= -1;
				shark->dir = 1;

				if (next_x >= R)
				{
					next_x = (2 * R) - 2 - next_x;
					shark->dir = 0;
				}
			}
		}
		// 가로로 움직이는 경우
		else
		{
			speed %= ((C - 1) * 2);

			next_y += speed * move_y[shark->dir];

			// 움직인 다음 범위를 초과한 경우 조정
			if (next_y >= C)
			{
				next_y = (2 * C) - 2 - next_y;
				shark->dir = 3;

				if (next_y < 0)
				{
					next_y *= -1;
					shark->dir = 2;
				}
			}
			else if (next_y < 0)
			{
				next_y *= -1;
				shark->dir = 2;

				if (next_y >= C)
				{
					next_y = (2 * C) - 2 - next_y;
					shark->dir = 3;
				}
			}

		}
		shark->pos_x = next_x;
		shark->pos_y = next_y;

		// 이동한 위치에 이미 상어가 위치해 있는 경우
		if (next_board[next_x][next_y] != -1)
		{
			Shark* prev_shark = &sharks[next_board[next_x][next_y]];

			// 이미 있는 상어와 크기를 비교한다.
			if (shark->size > prev_shark->size)
			{
				next_board[next_x][next_y] = idx;
				prev_shark->alive = false;
			}
			else
			{
				shark->alive = false;
			}
		}
		// 이동한 위치에 이미 상어가 위치해 있지 않은 경우
		else
		{
			next_board[next_x][next_y] = idx;
		}
	}

	copy(&next_board[0][0], &next_board[0][0] + 102 * 102, &board[0][0]);

	memset(next_board, -1, sizeof(next_board));
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> R >> C >> M;

	memset(board, -1, sizeof(board));
	memset(next_board, -1, sizeof(board));

	for (int i = 0; i < M; ++i)
	{
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;

		sharks.push_back({ r - 1, c - 1, s, d - 1, z, true });

		board[r - 1][c - 1] = i;
	}

	for (int person = 0; person < C; ++person)
	{
		fishing(person);
		move_sharks();
	}

	cout << answer;

	return 0;
}