[알고리즘] 낚시왕

포인트

• 사람이 낚시 -> 상어가 움직임 -> 상어가 상어를 잡아먹음
• 상어는 상어를 잡아먹는다고 커지지 않는다. (본인이 헷갈렸음)
• 그래도 무작정 푸는 것보다 10분 ~ 15 분 읽어보고 어떻게 할지 작성을 하면서 하면 어느 정도 문제가 익숙해진다. 급하게 풀지는 말자

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include<iostream>
#include<vector>
#include<algorithm>
 
#define endl "\n"
#define MAX 100 + 1
using std;
 
struct Shark_Info {
    int x;
    int y;
    int speed;
    int direction;
    int Size;
    int num;
};
 
int n, m, k, answer;
vector<int> map[MAX][MAX];
vector<Shark_Info> sharks;
 
int dx[] = {0, -1, 1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};
 
bool cmp(int A, int B) {
    if (sharks[A].Size > sharks[B].Size) return true;
    return false;
}
 
 
bool check() {
    for (int i = 0; i < sharks.size(); i++) { //상어가 다 죽을 수 도 있으니까
        if (sharks[i].Size != 0) return false;
    }
    return true;
}
 
void fishing(int index) {
    for (int i = 1; i <= n; i++) { //행을 따라 다니면서
        if (!map[i][index].empty()) {
            answer+= sharks[map[i][index][0]].Size; // 낚시왕이 잡은 상어의 크기
            sharks[map[i][index][0]].Size = 0;
            map[i][index].clear();
            break;
        }
    }
}
 
void move() {
    for (int i = 0; i < sharks.size(); i++) { //어차피 상어는 1마리
        if (sharks[i].Size == 0) continue;
        int x = sharks[i].x;
        int y = sharks[i].y;
        map[x][y] = {};
    } // 상어의 위치를 전부 알고 있으니까 현재 맵에 있는 상어의 위치를 전부 지운다.
 
    for (int i = 0; i < sharks.size(); i++) {
        if (sharks[i].Size == 0) continue;
        int x = sharks[i].x;
        int y = sharks[i].y;
        int direction = sharks[i].direction;
        int Speed = sharks[i].speed;
 
        if (direction == 1 || direction == 2) {
            int rotate = (n - 1) * 2;
            if (Speed >= rotate) Speed = Speed % rotate; //어차피 다시 돌아오는 것인까
 
            for (int j = 0; j < Speed; j++) { // 초당이니까 스피드 만큼 전진을 할 수 있다.
                int nx = x + dx[direction];
                int ny = y + dy[direction];
                if (nx < 1) {  // 범위를 넘어간면 방향을 바꾼다.
                    direction = 2;
                    nx = nx + 2;
                }
                if (nx > n) { // 마찬가지로 범위를 넘어가면 방향을 바꾼다.
                    direction = 1;
                    nx = nx - 2;
                }
                x = nx;
                y = ny;
            }
        } else {
            int Rotate = (m - 1) * 2;
            if (Speed >= Rotate) Speed = Speed % Rotate;
 
            for (int j = 0; j < Speed; j++) {
                int nx = x + dx[direction];
                int ny = y + dy[direction];
                if (ny < 1) { // 범위 넘어가면 방향 전환
                    direction = 3;
                    ny = ny + 2;
                }
                if (ny > m) {
                    direction = 4;
                    ny = ny - 2;
                }
                x = nx;
                y = ny;
            }
        }
        //map에 다시 반영
        sharks[i].x = x;
        sharks[i].y = y;
        sharks[i].direction = direction;
        map[x][y].push_back(i); // 그리고 맵에 다시 넣어준다.
    }
}
 
void kill() { //인제 상어가 같은 칸에 있으면 잡아먹는다.
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (map[i][j].size() > 1) {
                sort(map[i][j].begin(), map[i][j].end(), cmp); // 상어가 큰 것 부터 칸에 있다.
                int bigShark = map[i][j][0];
                for (int k = 1; k < map[i][j].size(); k++) { //여러 마리 있을 수 있으니 상어가 잡아먹는다고 크기가 커지지 않는다.
                    sharks[map[i][j][k]].Size = 0; //상어 배열에서 상어를 죽인다.
                    sharks[map[i][j][k]].x = -1;
                    sharks[map[i][j][k]].y = -1;
                }
                map[i][j].clear();
                map[i][j].push_back(sharks[bigShark].num);
            }
        }
    }
}
 
int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        int x, y, s, d, z;
        cin >> x >> y >> s >> d >> z;
        sharks.push_back({x, y, s, d, z, i});
        map[x][y].push_back(i); // 상어는 같은 칸에 여러 마리가 있을 수 있다.
    }
 
    if (k == 0) {
        cout << 0 << endl;
        return 0;
    }
 
    for (int i = 1; i <= m; i++) { //사람은 열을 이동한다.
        if (check()) break;
        fishing(i); //상어를 잡고
        move(); //상어가 움직이며
        kill(); //상어가 자기보다 작은걸 잡아먹는다.
    }
    cout << answer << endl;
    return 0;
}
 

 

python

r, c, k = map(int, input().split())
sharks = []

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]


def change_dir(dir: int) -> int:
	if dir == 0:
		return 1
	elif dir == 1:
		return 0
	elif dir == 2:
		return 3
	elif dir == 3:
		return 2


for _ in range(k):
	x, y, speed, dir, z = map(int, input().split())
	sharks.append([x - 1, y - 1, speed, dir - 1, z])

eat_z = 0

for j in range(c):
	sharks.sort(key=lambda x: (x[1], x[0]))
	remove_index = -1
	for index, shark in enumerate(sharks):
		x, y, speed, dir, z = shark
		if j == y:
			eat_z += z
			remove_index = index
			
			break
	
	if remove_index >= 0:
		sharks.pop(remove_index)
	# 사냥
	check = dict()
	for shark in sharks:
		x, y, speed, dir, z = shark
		if dir == 2 or dir == 3:
			speed %= (c - 1) * 2
		if dir == 0 or dir == 1:
			speed %= (r - 1) * 2
		for _ in range(speed):
			if dir == 2 and y == c - 1:
				dir = change_dir(dir)
			if dir == 3 and y == 0:
				dir = change_dir(dir)
			if dir == 0 and x == 0:
				dir = change_dir(dir)
			if dir == 1 and x == r - 1:
				dir = change_dir(dir)
			
			nx, ny = x + dx[dir], y + dy[dir]
			x, y = nx, ny
		
		if (x, y) not in check:
			check[(x, y)] = [[x, y, speed, dir, z]]
		else:
			check[(x, y)].append([x, y, speed, dir, z])
	
	sharks.clear()
	for key, value in check.items():
		if len(value) >= 2:
			value.sort(key=lambda x: x[4], reverse=True)
			sharks.append(value[0])
		else:
			sharks.append(value[0])
print(eat_z)