[백준/BOJ] 백준 17143번 : 낚시왕
2021. 2. 8. 04:21ㆍ알고리즘 문제풀이
이 문제에서 주의해야 될 점은 상어가 움직이는 것인데, 상어가 이동하려고 하는 칸이 판의 경계를 넘는 경우 방향을 반대로 바꿔서 이동한다는 성질을 이용하면 현재 상어의 속력 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;
}
'알고리즘 문제풀이' 카테고리의 다른 글
[백준/BOJ] 백준 2352번 : 반도체 설계 (0) | 2021.02.08 |
---|---|
[백준/BOJ] 백준 12738번 : 가장 긴 증가하는 부분 수열 3 (0) | 2021.02.08 |
[백준/BOJ] 백준 6549번 : 히스토그램에서 가장 큰 직사각형 (0) | 2021.02.08 |
[백준/BOJ] 백준 2357번 : 최솟값과 최댓값 (0) | 2021.02.08 |
[백준/BOJ] 백준 1162번 : 도로포장 (0) | 2021.02.08 |