백준 17143번 낚시왕

문제 링크입니다: https://www.acmicpc.net/problem/17143

17143번: 낚시왕

상대적으로 쉬운 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. vector<pair<int, pair<int, int>>> graph[MAX][MAX] 벡터를 생성하여 해당 좌표에 {상어의 크기, {속도, 방향}}을 추가하는 방식으로 전처리를 진행합니다.

2. 우선, 낚시꾼이 이동하므로 낚시꾼의 x 좌표를 한 칸 움직여줍니다.

3. 낚시꾼이 이동한 x 좌표를 기준으로 y 좌표를 오름차순으로 탐색하며 상어가 있는지 확인하며 제일 먼저 탐색한 상어를 잡고 반복문을 빠져나옵니다.

4. 상어를 이동하는데, 큐에 상어의 좌표와 {상어의 크기, {속도, 방향}}을 넣어주고 해당 좌표에 있는 상어들을 모두 없애줍니다.

5. 큐에 넣은 상어들을 각각의 속도만큼 이동해주는데 벽에 마주할 경우 적절한 인덱싱을 통해 반대방향으로 돌아 움직일 수 있게 해줍니다.

6. 이동한 좌표에 상어를 추가하는데 해당 칸에 이미 자신보다 큰 상어가 있는 경우에는 추가해주지 않고 자신보다 작은 상어가 있으면 해당 상어를 쫒아내고 해당 칸에 들어갑니다.

7. 낚시꾼이 x 범위를 모두 이동할 동안 3 ~ 6번을 반복합니다.

 

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <queue>
	using namespace std;
	const int MAX = 100 + 1;
	typedef struct
	{
	int y, x;
	}Dir;
	Dir moveDir[4] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} }; //N S E W
	int R, C, M;
	int arr[MAX][MAX];
	vector<pair<int, pair<int, int>>> shark[MAX][MAX];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(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[r][c].push_back({ z, {s, d - 1} });
	}
	int cur = 0;
	int result = 0;
	for (int c = 0; c < C; c++)
	{
	cur++;
	//땅에 제일 가까운 상어 먹고
	for(int i=1; i<=R; i++)
	if (shark[i][cur].size())
	{
	result += shark[i][cur][0].first;
	shark[i][cur].clear();
	break;
	}
	//r, c, z, s, d
	queue<pair<pair<int, int>, pair<int, pair<int, int>>>> q;
	for (int i = 1; i <= R; i++)
	for (int j = 1; j <= C; j++)
	if (shark[i][j].size())
	{
	q.push({ {i, j}, {shark[i][j][0]} });
	shark[i][j].clear();
	}
	//상어가 움직인다
	while (!q.empty())
	{
	int y = q.front().first.first;
	int x = q.front().first.second;
	int size = q.front().second.first;
	int speed = q.front().second.second.first;
	int dir = q.front().second.second.second;
	q.pop();
	for (int i = 0; i < speed; i++)
	{
	//위 아래
	if (dir == 0 || dir == 1)
	{
	int next = y + moveDir[dir].y;
	if(!(1 <= next && next <= R))
	dir = 1 - dir;
	y += moveDir[dir].y;
	}
	//왼쪽 오른쪽ㄴ
	else
	{
	int next = x + moveDir[dir].x;
	if (!(1 <= next && next <= C))
	dir = 5 - dir;
	x += moveDir[dir].x;
	}
	}
	//이미 해당 칸에 상어가 있을 경우
	if (shark[y][x].size())
	{
	//해당 칸에 있는 상어 크기보다 자기가 더 클 경우에만 대체
	if (shark[y][x][0].first < size)
	{
	shark[y][x].clear();
	shark[y][x].push_back({ size,{ speed, dir } });
	}
	}
	//해당 칸에 상어가 없는 경우 바로 추가
	else
	shark[y][x].push_back({ size,{ speed, dir } });
	}
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~