어흥
[백준 17143] 낚시왕 (C++) 본문
문제 링크: www.acmicpc.net/problem/17143
1. 주의할 점
- 상어가 격자판의 끝에 도달할 경우, 방향을 바꿔서 전진하는 과정 구현
- 상어에 대한 정보의 표현 방법(배열 or 벡터 등등)
2. 구현
- 상어에 대한 정보를 입력받을 때 방향의 경우, 따로 설정한 방향으로 변환한다(0~3: 상우하좌 순서). 방향값 변환 이후, Shark 벡터에 상어에 대한 정보를 저장한다
- Player 변수를 통해 현재 낚시왕의 위치를 표시한다
- checkDown() 함수를 통해 현재 낚시왕의 아래에 물고기가 있다면, 가장 위에 있는 물고기의 크기만큼 Result에 더하고 해당 물고기를 사망처리한다
- sharkMv() 함수의 초기에 Arr[][] 배열을 전부 -1로 초기화하여 모든 상어의 이동후 중복 여부를 체크한다
- 상어가 현재 방향으로 진행하는 거리: dx[cd]*cs 와 dy[cd]*cs다. 이때, cs의 값이 Row나 Col에 비해 매우 클 수 있기 때문에, 1회 왕복 거리인 2*(Col-1) 와 2*(Row-1)로 나눈 나머지만큼 추가 이동한다고 한다(사소한 시간 단축 차이)
- 현재 위치에서 추가 이동거리만큼 이동했을 때의 위치를 ny, nx에 저장하고 ny,nx가 격자판의 범위 밖에 있다면 While()문을 통해 위치와 진행방향을 수정한다(While문이 중요!)
- 이동한 위치의 Arr[][] 값을 통해 상어의 유무를 판단하고 이미 상어가 존재하지 않으면 이동을, 이미 상어가 존재한다면 크기를 비교해서 큰 상어 생존 + 작은 상어 사망처리를 수행한다
#include <iostream>
#include <vector>
using namespace std;
struct info {
int y, x, s, dir, val;
bool dead = false;
};
info tmp;
int arr[101][101];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int result = 0, player = 0, row, col, num, x, y, val, s, dir;
vector<info> shark;
void checkDown() {
int idx = -1, height = row + 1;
for (int i = 0; i < shark.size(); i++) {
if (shark[i].dead) continue;
int sy = shark[i].y;
int sx = shark[i].x;
if (player == sx && sy < height) {
height = sy;
idx = i;
}
}
if (idx != -1) { //잡은 경우
result += shark[idx].val;
shark[idx].dead = true;
}
}
void sharkMv() {
for (int i = 1; i <= row; i++)
for (int j = 1; j <= col; j++)
arr[i][j] = -1;
for (int i = 0; i < shark.size(); i++) {
if (shark[i].dead) continue;
int cx = shark[i].x;
int cy = shark[i].y;
int cs = shark[i].s;
int cd = shark[i].dir;
int cv = shark[i].val;
int nd = cd;
int nx = cx + (dx[cd] * cs) % (2 * (col - 1));
int ny = cy + (dy[cd] * cs) % (2 * (row - 1));
while (nx < 1 || nx > col) {
if (nx < 1) {
nx = 2 - nx;
nd = (nd + 2) % 4;
}
if (nx > col) {
nx = 2 * col - nx;
nd = (nd + 2) % 4;
}
}
while (ny < 1 || ny > row) {
if (ny < 1) {
ny = 2 - ny;
nd = (nd + 2) % 4;
}
if (ny > row) {
ny = 2 * row - ny;
nd = (nd + 2) % 4;
}
}
val = arr[ny][nx];
if (val == -1) { //해당 자리에 아무 상어도 없는 경우
arr[ny][nx] = i;
shark[i].x = nx;
shark[i].y = ny;
shark[i].dir = nd;
}
else { //해당 자리에 다른 상어가 있는 경우
if (shark[val].val > cv) shark[i].dead = true;
else {
arr[ny][nx] = i;
shark[val].dead = true;
shark[i].x = nx;
shark[i].y = ny;
shark[i].dir = nd;
}
}
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> row >> col >> num;
for (int i = 0; i < num; i++) {
cin >> y >> x >> s >> dir >> val;
if (dir == 1) dir = 0;
else if (dir == 3) dir = 1;
else if (dir == 4) dir = 3;
shark.push_back({ y,x,s,dir,val });
}
while (player <= col) {
player++;
checkDown();
sharkMv();
}
cout << result;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준 2531] 회전 초밥 (C++) (0) | 2021.04.27 |
---|---|
[백준 17142] 연구소 3 (C++) (0) | 2021.04.21 |
[백준 16920] 확장 게임 (C++) (0) | 2021.04.19 |
[백준 20058] 마법사 상어와 파이어스톰 (C++) (0) | 2021.04.15 |
[백준 20057] 마법사 상어와 토네이도 (C++) (0) | 2021.04.14 |