백준 17143번 _ 낚시왕

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

17143번: 낚시왕

 

자료선언

class Shark
{
public:
	int speed;
	int dir;
	int size;
	Shark(int speed_in, int dir_in, int size_in)
		:speed(speed_in), dir(dir_in), size(size_in)
	{}
};

vector<vector<vector<Shark>>> MAP;
int R, C, M;
vector<pair<int, int>>dir = { {0,0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

 

---

 

1. 풀이방법

 

 이 문제는 상어들의 움직임이 아주 중요한 문제이다. 그외에는 어렵지 않으니 상어 움직임에 대해서만 설명하겠다

 

 일단 입력시 아래 코드처럼 상,하의 방향이면 (R-1)*2로 모듈러연산을 해주고, 좌,우에는 (C-1)*2로 모듈러 연산해준다.

if(d == 1 || d == 2)
	MAP[r][c].push_back(move(Shark(s% ((R - 1) * 2), d, z)));
else
	MAP[r][c].push_back(move(Shark(s % ((C - 1) * 2), d, z)));

 이 부분이 아주 중요한데 왜냐하면 주어지는 상어의 s의 범위는 0 ~1000이기 때문에 s가 크다면 이런식으로 좌우나 상하로 의미없는 반복을 할수도 있다.

 

 이제 왜 상하는 (R-1)*2고, 좌우는 (C-1)*2인가에 대해서 궁금할텐데 이건 간단하다.

 그림에서 보다시피 움직인 이후에 제자리로 돌아오려면 각각 (R-1)*2, (C-1)*2의 거리가 필요하기 때문이다.

 

 이제 이것까지 했다면 움직임을 구현하는것 자체는 간단하다.

vector<pair<int, int>>dir = { {0,0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

 방향에 따른 좌표변화량을 미리 맞춰주고

 

for (int k = 0; k < speed; k++)
{
	ny += dir[d].first;
	nx += dir[d].second;

	//바깥으로 나갔다면 반대로 ㄱㄱ
	if (!(ny >= 1 && nx >= 1 && ny <= R && nx <= C))
	{
		d = dirChange(d);
		ny += (2 * dir[d].first);
		nx += (2 * dir[d].second);
	}
}

 모듈러 연산된 스피드값대로 상어를 움직여준다. 이때 벽에 부딪치면 반대편으로 두번가면 (넘어간위치 -> 원래위치 -> 원하는위치) 우리가 원하는 동작이 완성된다.

 

---

 

2.코드

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Shark
{
public:
	int speed;
	int dir;
	int size;
	Shark(int speed_in, int dir_in, int size_in)
		:speed(speed_in), dir(dir_in), size(size_in)
	{}
};

vector<vector<vector<Shark>>> MAP;
int R, C, M;
vector<pair<int, int>>dir = { {0,0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

void mapInit(vector<vector<vector<Shark>>>& map)
{
	map.resize(R + 2);
	for (int i = 1; i <= R; i++)
		map[i].resize(C + 2);
}

int dirChange(int d)
{
	if (d == 1)
		return 2;
	if (d == 2)
		return 1;
	if (d == 3)
		return 4;
	if (d == 4)
		return 3;
}

void SharkMove()
{
	vector<vector<vector<Shark>>> tmpMap;
	mapInit(tmpMap);
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			if (MAP[i][j].size() == 0)
				continue;
			for (auto& shark : MAP[i][j])
			{
				int speed = shark.speed;
				int d = shark.dir;
				int size = shark.size;
				int ny = i;
				int nx = j;

				for (int k = 0; k < speed; k++)
				{
					ny += dir[d].first;
					nx += dir[d].second;

					//바깥으로 나갔다면 반대로 ㄱㄱ
					if (!(ny >= 1 && nx >= 1 && ny <= R && nx <= C))
					{
						d = dirChange(d);
						ny += (2 * dir[d].first);
						nx += (2 * dir[d].second);
					}
				}

				tmpMap[ny][nx].push_back(Shark(speed, d, size));
			}
		}
	}

	MAP = move(tmpMap);
}

bool compare(const Shark& first, const Shark& second)
{
	return first.size > second.size;
}

void SharkEatInSameArea()
{
	for (int i = 1; i <= R; i++)
	{
		for (int j = 1; j <= C; j++)
		{
			if (MAP[i][j].size() == 0 && MAP[i][j].size() == 1)
				continue;
			if (MAP[i][j].size() > 1)
			{
				vector<Shark> tmp = move(MAP[i][j]);
				sort(begin(tmp), end(tmp), compare);
				MAP[i][j].push_back(tmp[0]);
			}
		}
	}
}

int fishing()
{
	int cnt = 0;
	for (int people = 1; people <= C; people++)
	{
		for (int i = 1; i <= R; i++)
		{
			if (MAP[i][people].size() == 0)
				continue;
			cnt += MAP[i][people][0].size;
			MAP[i][people].clear();
			break;
		}
		SharkMove();
		SharkEatInSameArea();
	}
	return cnt;
}

int main()
{
	cin >> R >> C >> M;
	int r, c, s, d, z;
	mapInit(MAP);
	for (int i = 0; i < M; i++)
	{
		cin >> r >> c >> s >> d >> z;
		if(d == 1 || d == 2)
			MAP[r][c].push_back(move(Shark(s% ((R - 1) * 2), d, z)));
		else
			MAP[r][c].push_back(move(Shark(s % ((C - 1) * 2), d, z)));
	}
	SharkEatInSameArea();
	cout << fishing();

	return 0;
}

 

 

---

 

3. 후기

 

 이런 문제는 한끝차이로 틀려서 인터넷으로 풍부한 힌트들을 알아보면 쉽지만 시험에 가서는 별로 자신이 없다. ㅠ