백준 17143 낚시왕 (c++) : 피너클

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

17143번: 낚시왕

귀찮은 구현문제다.

하나라도 삐끗하면 지금까지 짠 모든 코드가 물거품이 되는 무서운 문제다.

위처럼 된다.

만약 계속해서 틀린다면 낚시 -> 상어 움직임 -> 상어 끼리 싸우기 순으로 했는지 확인해봐라

나는 상어 움직임 -> 상어 싸움 -> 낚시 순서로 여러번 돌려서 위처럼 되었다.

int r, c, m;
vector<int> map[201][201];
vector<pair<int, int>> map_chk;
class shark {
public:
	int r, c, s, d, z;
};
vector<shark> v;

사용할 변수다.

map[i][j]에는 현재 위치가 (i, j)인 상어의 인덱스가 들어간다.

map_chk[i] = {a, b}라면 {a, b}위치에 상어가 2마리 이상 있다는 뜻이다.

void move_up(int idx) {
	int ud = (v[idx].d == 1 ? -1 : 1);
	for (int i = 0; i < v[idx].s; i++) {
		if (v[idx].r == r) ud = -1, v[idx].d = 1;
		else if (v[idx].r == 1) ud = 1, v[idx].d = 2;
		v[idx].r += ud;
	}
}

move_up함수다. v[idx]를 움직인다.

ud는 상어가 위로 움직여야하면 -1이 되고 아래로 움직여야 한다면 1이 된다.

그후 상어의 속도만큼 반복문을 돌리며 경계에 다으면 ud와 d를 바꿔준다.

이를 move_down, move_right, move_left도 만들어주면 된다.

void move(int idx) {
	if (v[idx].d == 1) move_up(idx);
	else if (v[idx].d == 2) move_down(idx);
	else if (v[idx].d == 3) move_right(idx);
	else if (v[idx].d == 4) move_left(idx);
}

이를 하나로 모으면 move함수가 된다.

v[idx]의 상어가 움직이는 방향에 맞춰 함수를 실행시킨다.

void fight() {
	for (int i = 0; i < map_chk.size(); i++) {
		int r = map_chk[i].first, c = map_chk[i].second;
		for (int j = 0; j < map[r][c].size() - 1; j++) {
			shark s1 = v[map[r][c][j]];
			shark s2 = v[map[r][c][j + 1]];
			if (s1.z > s2.z) swap(v[map[r][c][j]], v[map[r][c][j + 1]]);
			v[map[r][c][j]].r = -1;
			v[map[r][c][j]].c = -1;
			v[map[r][c][j]].s = -1;
		}
	}
}

fight함수다.

map_chk의 크기 만큼 반복문을 돌린다.

r과 c에 map_chk의 값을 집어넣는다. 현재 map[r][c]에 상어가 2마리 이상 들어있다는 뜻이다.

이제 map[r][c]만큼 반복문을 돌린다. 크기가 작은 상어는 위치를 -1, -1로 보내고 속도를 -1로 바꿀것이다.

s1과 s2에 상어를 담는다. 이중 s1상어를 없엘것이다. 만약 s1상어가 s2상어보다 크기가 크다면 둘을 swap한다.

그후 s1상어를 -1, -1로 옮기고 속도를 -1로 바꾼다. 이러면 마지막에 가장 큰 상어만 남게된다.

cin >> r >> c >> m;
for (int i = 0; i < m; i++) {
    int r, c, s, d, z;
    cin >> r >> c >> s >> d >> z;
    shark q = { r, c, s, d, z };
    v.push_back(q);
}
cout << solve(1) << endl;

main함수다.

값들을 입력받고 solve함수를 돌리면된다.

int solve(int now) {
	if (now == c + 1) return 0;
	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 101; j++)
			map[i][j].clear();
	map_chk.clear();

solve함수다. now는 현재 낚시왕이 있는 위치다.

만약 낚시꾼이 c+1에 있다면 격자판에서 나갔다는것이다. 바로 종료해준다.

그후 map과 map_chk를 초기화해준다.

	int eat = 0;
	vector<pair<int, int>> can;
	for (int i = 0; i < m; i++) {
		if (v[i].s == -1) continue;
		if (v[i].c == now) {
			can.push_back({ v[i].r, i });
		}
	}
	sort(can.begin(), can.end());

eat는 낚시꾼이 잡을 상어의 크기다.

can에는 낚시꾼이 잡을수있는 상어의 깊이와 인덱스가 들어간다.

v[i]의 속도가 -1이라면 이미 먹힌 상어라는 뜻이니 continue해주고

만약 v[i]의 위치가 now와 같다면 can에 넣어준다.

그후 can을 정렬해준다.

	if (!can.empty()) {
		int idx = can[0].second;
		eat += v[idx].z;
		v[idx].r = -1, v[idx].c = -1, v[idx].s = -1;
	}

그후 can이 비어있지 않다면 가장 앞에 있는 상어를 잡아준다.

깊이 순으로 정렬되었으니 가장 앞에 있는 상어가 가장 표면에 가까이 있는 상어다.

eat에 상어의 크기를 넣어주고 상어의 위치와 속도를 바꿔준다.

	for (int i = 0; i < m; i++) {
		if (v[i].s == -1) continue;
		move(i);
		map[v[i].r][v[i].c].push_back(i);
		if (map[v[i].r][v[i].c].size() == 2) map_chk.push_back({ v[i].r, v[i].c });
	}
	fight();

낚시꾼이 상어를 잡았으니 이젠 상어가 이동하고 싸울 차례다.

반복문을 돌리며 상어의 속도가 -1이 아니라면 움직인다.

움직인후 현재 상어의 위치의 map에 상어의 인덱스를 넣고 만약 상어 위치 map의 사이즈가 2라면 map_chk에 넣어준다.

그후 fight함수를 돌려준다.

	return eat + solve(now + 1);
}

마지막으로 현재 잡은 상어와 solve(now + 1)을 리턴해주면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int r, c, m;
vector<int> map[201][201];
vector<pair<int, int>> map_chk;
class shark {
public:
	int r, c, s, d, z;
};
vector<shark> v;

void move_up(int idx) {
	int ud = (v[idx].d == 1 ? -1 : 1);
	for (int i = 0; i < v[idx].s; i++) {
		if (v[idx].r == r) ud = -1, v[idx].d = 1;
		else if (v[idx].r == 1) ud = 1, v[idx].d = 2;
		v[idx].r += ud;
	}
}
void move_down(int idx) {
	int ud = (v[idx].d == 1 ? -1 : 1);
	for (int i = 0; i < v[idx].s; i++) {
		if (v[idx].r == r) ud = -1, v[idx].d = 1;
		else if (v[idx].r == 1) ud = 1, v[idx].d = 2;
		v[idx].r += ud;
	}
}
void move_right(int idx) {
	int lr = (v[idx].d == 4 ? -1 : 1);
	for (int i = 0; i < v[idx].s; i++) {
		if (v[idx].c == c) lr = -1, v[idx].d = 4;
		else if (v[idx].c == 1) lr = 1, v[idx].d = 3;
		v[idx].c += lr;
	}
}
void move_left(int idx) {
	int lr = (v[idx].d == 4 ? -1 : 1);
	for (int i = 0; i < v[idx].s; i++) {
		if (v[idx].c == c) lr = -1, v[idx].d = 4;
		else if (v[idx].c == 1) lr = 1, v[idx].d = 3;
		v[idx].c += lr;
	}
}

void move(int idx) {
	if (v[idx].d == 1) move_up(idx);
	else if (v[idx].d == 2) move_down(idx);
	else if (v[idx].d == 3) move_right(idx);
	else if (v[idx].d == 4) move_left(idx);
}

void fight() {
	for (int i = 0; i < map_chk.size(); i++) {
		int r = map_chk[i].first, c = map_chk[i].second;
		for (int j = 0; j < map[r][c].size() - 1; j++) {
			shark s1 = v[map[r][c][j]];
			shark s2 = v[map[r][c][j + 1]];
			if (s1.z > s2.z) swap(v[map[r][c][j]], v[map[r][c][j + 1]]);
			v[map[r][c][j]].r = -1;
			v[map[r][c][j]].c = -1;
			v[map[r][c][j]].s = -1;
		}
	}
}

int solve(int now) {
	if (now == c + 1) return 0;
	for (int i = 0; i < 101; i++)
		for (int j = 0; j < 101; j++)
			map[i][j].clear();
	map_chk.clear();
	int eat = 0;
	vector<pair<int, int>> can;
	for (int i = 0; i < m; i++) {
		if (v[i].s == -1) continue;
		if (v[i].c == now) {
			can.push_back({ v[i].r, i });
		}
	}
	sort(can.begin(), can.end());
	if (!can.empty()) {
		int idx = can[0].second;
		eat += v[idx].z;
		v[idx].r = -1, v[idx].c = -1, v[idx].s = -1;
	}
	for (int i = 0; i < m; i++) {
		if (v[i].s == -1) continue;
		move(i);
		map[v[i].r][v[i].c].push_back(i);
		if (map[v[i].r][v[i].c].size() == 2) map_chk.push_back({ v[i].r, v[i].c });
	}
	fight();
	return eat + solve(now + 1);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.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 q = { r, c, s, d, z };
		v.push_back(q);
	}
	cout << solve(1) << endl;
}

전체코드다.