[백준/BOJ] 백준 17143번 : 낚시왕

2021. 2. 8. 04:21알고리즘 문제풀이

www.acmicpc.net/problem/17143

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다.

www.acmicpc.net

이 문제에서 주의해야 될 점은 상어가 움직이는 것인데, 상어가 이동하려고 하는 칸이 판의 경계를 넘는 경우 방향을 반대로 바꿔서 이동한다는 성질을 이용하면 현재 상어의 속력 s가 어떤 속력일때와 같은 위치로 이동하는지를 알아내 실제 이동하는 칸을 줄일 수 있다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <map>
using namespace std;

int R, C, M;
struct shark {
	int s; //속력
	int d; //이동 방향
	int z; //크기
};
map<int, shark> shark_map[101];
map<int, shark>::iterator it;
int dxdy[5][2] = { {0,0},{-1,0},{1,0},{0,1},{0,-1} };

void Move_shark()
{
	queue<pair<pair<int, int>, shark>> q; //상어 위치, 정보 저장

	for (int i = 1; i <= C; i++)
	{
		if (shark_map[i].size() != 0)
		{
			for (it = shark_map[i].begin(); it != shark_map[i].end(); it++)
			{
				pair<int, int> this_shark_point = make_pair((*it).first, i);
				shark this_shark_info = (*it).second;

				q.push(make_pair(this_shark_point, this_shark_info));
			}
		}
		shark_map[i].clear();
	}

	while (!q.empty())
	{
		pair<int, int> here_shark_point = q.front().first;
		shark here_shark_info = q.front().second;
		q.pop();

		int same_s; //현재 상어의 속력 s가 어떤 속력일때와 같은 위치인지 

		if (here_shark_info.d == 1)
			same_s = here_shark_info.s % ((R - 1) * 2);

		else if (here_shark_info.d == 2)
			same_s = here_shark_info.s % ((R - 1) * 2);

		else if (here_shark_info.d == 3)
			same_s = here_shark_info.s % ((C - 1) * 2);

		else if (here_shark_info.d == 4)
			same_s = here_shark_info.s % ((C - 1) * 2);

		pair<int, int> there_shark_point = here_shark_point;
		shark there_shark_info = here_shark_info;

		for (int i = 0; i < same_s; i++)
		{
			there_shark_point = make_pair(here_shark_point.first + dxdy[there_shark_info.d][0], here_shark_point.second + dxdy[there_shark_info.d][1]);

			if (there_shark_point.first >= 1 && there_shark_point.first <= R && there_shark_point.second >= 1 && there_shark_point.second <= C)
			{
				here_shark_point = there_shark_point;
				continue;
			}

			else
			{
				if (there_shark_info.d == 1)
				{
					there_shark_point.first++;
					there_shark_point.first++;

					there_shark_info.d = 2;
				}

				else if (there_shark_info.d == 2)
				{
					there_shark_point.first--;
					there_shark_point.first--;

					there_shark_info.d = 1;
				}

				else if (there_shark_info.d == 3)
				{
					there_shark_point.second--;
					there_shark_point.second--;

					there_shark_info.d = 4;
				}

				else if (there_shark_info.d == 4)
				{
					there_shark_point.second++;
					there_shark_point.second++;

					there_shark_info.d = 3;
				}

				here_shark_point = there_shark_point;
			}

		}

		if (shark_map[there_shark_point.second].count(there_shark_point.first) != 0) //해당 위치에 상어가 존재할때
		{
			if (shark_map[there_shark_point.second][there_shark_point.first].z > there_shark_info.z) //존재하는 상어가 더 클때
				continue;

			else
				shark_map[there_shark_point.second][there_shark_point.first] = there_shark_info; //크기가 더 큰 상어로 업데이트
		}

		else
			shark_map[there_shark_point.second].insert(make_pair(there_shark_point.first, there_shark_info));
	}
}


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

	int result = 0;

	cin >> R >> C >> M;

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

		cin >> r >> c >> s >> d >> z;
		shark this_shark = { s,d,z }; 
		shark_map[c].insert(make_pair(r, this_shark)); //열마다 행에 맞는 상어의 정보 저장
	}

	for (int i = 1; i <= C; i++)
	{
		if (shark_map[i].size() > 0)
		{
			result += (*(shark_map[i].begin())).second.z; //해당 열의 가장 가까운 상어 잡기
			shark_map[i].erase(shark_map[i].begin());
		}

		Move_shark(); //상어의 움직임
	}

	cout << result;

	return 0;
}