[BOJ] 17143. 낚시왕

[문제]

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

17143번: 낚시왕

[풀이]

 

1) 1초 프로세스

• 낚시왕은 오른쪽으로 한 칸 움직인다. 
• 낚시왕이 위치한 열 중 땅에서 가장 가까운 곳에 위치한 상어를 잡는다. 
• 상어는 정해진 속력과 방향으로 움직인다. 

2) 낚시왕은 가장 오른쪽 열, 오른쪽 칸으로 이동하면 멈춘다. 

 

3) 상어들은 격자판 경계에 부딪히면 방향을 반대로 전환하여 움직인다. (여기서 혼동하지 말아야 할 점은 이동을 하다 부딪히면 그때 방향을 바꾼다는 점이다. (처음부터 부딪힐걸 계산하고 방향을 바꿔 움직이면 답이 다르게 나온다)) 

 

4) 이동한 좌표에 이미 상어가 존재한다면 크기가 큰 상어가 다른 상어들을 모두 잡아먹고 그 자리를 차지한다. (결국 한 칸에는 상어 1마리만 위치하게 된다.)

 

반드시 한 칸에 한 마리만 존재한다는 걸 보장받는다면 vector를 x, y좌표로 이차원 배열로 만들고 0번 인덱스 안에 size, speed , dir을 넣는다면 0번 인덱스만 살펴봐도 바로 값이 나오기 때문에 편리하다. 

 

5) 이동한 칸에 상어가 없다면 그 자리에 그대로 위치시킨다. 

 

6) 이 과정을 낚시왕이 0번인덱스부터 c에 위치할때까지 반복한다. 

 

7) 결과는 잡은 상어의 무게 합

 

---

#include <iostream> #include <vector> #include <queue> using namespace std; int r, c, m; typedef struct Shark { int s, d, z; } S; typedef struct Q { int x, y; S shark; Q(int _x, int _y, S _s) : x(_x), y(_y), shark(_s){}; }; vector<S> map[101][101]; int dx[4] = {-1,1,0,0}, dy[4] = {0,0,1,-1}; void moveShark() { queue<Q> q; for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { if (map[i][j].size()) { q.push(Q(i, j, map[i][j][0])); map[i][j].clear(); } } } while(!q.empty()) { int x = q.front().x; int y = q.front().y; S shark = q.front().shark; q.pop(); for (int i = 0; i < shark.s; i++) { if (shark.d == 0 || shark.d == 1) { int nx = x + dx[shark.d]; if (!(1<= nx && nx <= r)) { shark.d = 1-shark.d; } x += dx[shark.d]; } else { int ny = y + dy[shark.d]; if (!(1<= ny && ny <= c)) { shark.d = 5-shark.d; } y += dy[shark.d]; } // int nx = x + dx[shark.d]; // int ny = y + dy[shark.d]; // if (nx <= 0 || nx > r || ny <= 0 || ny > c ) { // shark.d = shark.d < 2 ? 1-shark.d : 5-shark.d; // } // x+=dx[shark.d]; // y+=dy[shark.d]; } if (map[x][y].size()) { //이미 다른 상어가 잇는 경우 //크기 비교 if (map[x][y][0].z < shark.z) { map[x][y].clear(); map[x][y].push_back(shark); } } else { map[x][y].push_back(shark); } } } int catchShark(int col) { int res = 0; for (int j = 1; j <= r; j++) { if (map[j][col].size()) { //이 상어 먹음 res = map[j][col][0].z; map[j][col].clear(); break; } } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> r >> c >> m; int x, y, s, d, z; for (int i = 0; i < m; i++) { cin >> x >> y >> s >> d >> z; S shark; shark.s = s; shark.d = d-1; shark.z = z; map[x][y].push_back(shark); } int res = 0; for (int i = 1; i <= c; i++) { //총 c번의 기회 res += catchShark(i); moveShark(); } cout << res<< '\n'; return 0; }