<Beakjoon> #17143 BFS, compare 구조체 정의_낚시왕 c++

Google 아니고 Joogle·2022년 3월 11일

SAMSUNG SW Test

목록 보기

23/39

`✏️ Summary`

낚시왕은 처음 (0,0)위치에 있다가 오른쪽으로 한 칸 이동한다
낚시왕이 있는 열에서 가장 가까운 상어를 잡아 먹는다
상어는 자신이 가지고 있는 방향으로 속도만큼 이동한다
상어가 이동중 벽에 부딪칠경우 방향을 반대로 바꿔서 이동한다
상어가 모두 이동을 마친 후 한 칸에 두 마리 이상이 있으면 크기가 큰 상어가 나머지 상어를 모두 잡아 먹는다

📝 1. Initialize

상어의 위치(r,c), 속도(s), 방향(d), 크기(z)를 담을 구조체를 정의하고, 추가로 이 상어가 살아 있는지를 표시하기 위해 bool live도 정의한다 (초기값은 모두 살아있는 상태)
struct SHARK {
	int r, c;
	int s, d, z;
	bool live=true;
};
vector<SHARK> shark;
map상에서 한 공간에는 2개 이상의 상어가 있을 수도 있기 때문에 상어의 index를 여러 개 저장할 수 있는 map을 정의한다
vector<int> map[MAX][MAX];
방향이 위,아래,오른쪽,왼쪽 순으로 1,2,3,4로 나타내지기 때문에 방향을 나타낼 때도 1번 째부터 채워지게 만든다
int dy[] = { 0,-1,1,0,0 };
int dx[] = { 0,0,0,1,-1 };

📝2. Input Data

shark에 정보를 넣을 때, shark가 있는 위치 map[r][c]에 shark가 몇 번째 shark인 지 넣어준다
void input() {
	cin >> R >> C >> M;
	for (int i = 0; i < M; i++) {
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		shark.push_back({ r,c,s,d,z});
		map[r][c].push_back(i);
	}
}

📝3. Fishing

낚시왕이 (0,x) 위치에 있을 때, map[1][x]~map[R][x] 사이에 상어가 있으면 해당 상어의 사이즈만큼 더해준다

해당 위치에 있는 상어를 없애주고, 해당 상어의 live상태를 false로 바꾸어준다
void fishing(int x) {
	for (int i = 1; i <= R; i++) {
		if (map[i][x].size() != 0) {
			int idx = map[i][x][0];
			sum += shark[idx].z;
			shark[idx].live = false;
			map[i][x].clear();
			break;
		}
	}
}

📝4. Move Shark

상어를 움직이기 전에 map을 모두 초기화 해준다
(moveShark 함수에서 움직인 후 상어를 map에 넣어주려고)

모든 상어를 움직이게 하는데, 이 때 shark의 live==false 이거나 size==0인 경우에는 움직이지 않는다
(size==0이면 바로 상어를 map상의 위치에 넣어준다)
if (shark[i].s == 0) 
	map[shark[i].r][shark[i].c].push_back(i);
상어의 speed만큼 상어 방향으로 한 칸씩 차례대로 움직이고, 만약 벽에 부딪칠 경우 방향을 바꿔준다

상어의 속도는 최대 1000이고, 최대 상어는 100*100개가 있을 수 있으므로 매번 모든 상어를 이렇게 움직일 경우 시간 초과가 난다. 따라서 speed가 클 경우 이를 줄이는 방법을 생각해야 한다.

상어가 위, 아래로 움직이는 경우 (R*2)-2, 상어가 왼쪽, 오른쪽으로 움직이는 경우 (C*2)-2로 현재 속도를 나눈다
if (dir == 1 || dir == 2)
	speed = speed % (R * 2 - 2);
else if (dir == 3 || dir == 4)
	speed = speed % (C * 2 - 2);
이렇게 구한 speed만큼 한 칸씩 움직이는데, 움직이는 도중 만약 벽에 부딪친다면, 즉, map의 범위를 벗어 난다면 방향을 반대로 바꾸고 다시 돌아와야 한다
//out of range= => change direction and move back

if (ny<1 || ny>R || nx<1 || nx>C) {
	switch (dir) {
	case 1: dir = 2; break;
	case 2: dir = 1; break;
	case 3: dir = 4; break;
	case 4: dir = 3; break;
	}
	ny = ny + dy[dir] * 2;
	nx = nx + dx[dir] * 2;
}
상어의 움직임이 끝나면 현재 상어가 있는 좌표에 상어의 index를 넣어준다
map[cur_y][cur_x].push_back(n);

📝5. Kill Shark

모든 좌표를 돌면서 map[i][j].size()>1 즉, 여러 상어가 같은 위치에 있을 경우 사이즈가 가장 큰 상어가 나머지 상어들을 잡아 먹는다

map[i][j]에 있는 상어들을 사이즈를 기준으로 내림차순으로 정렬한다.
bool compare(int A, int B) {
	if (shark[A].z > shark[B].z) return true;
	return false;
}
if (map[i][j].size() >1) {
	sort(map[i][j].begin(), map[i][j].end(), compare);
map[i][j][0]에 사이즈가 가장 큰 상어가 저장되고, 나머지 상어들의 live=false로 바꾸어주고, map을 비운 뒤, map[i][j][0]에 있던 값을 다시 넣어준다
void killShark() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (map[i][j].size() >1) {
				sort(map[i][j].begin(), map[i][j].end(), compare);

				int liveIdx = map[i][j][0];

				for (int k = 1; k < map[i][j].size(); k++)
					shark[map[i][j][k]].live = false;
				map[i][j].clear();
				map[i][j].push_back(liveIdx);
			}
		}
	}
}

`⌨️전체코드`

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

using namespace std;

const int MAX = 1001;

int dy[] = { 0,-1,1,0,0 };
int dx[] = { 0,0,0,1,-1 };

int R, C, M;
int sum = 0;
vector<int> map[MAX][MAX];

struct SHARK {
	int r, c;
	int s, d, z;
	bool live=true;
};
vector<SHARK> shark;

bool compare(int A, int B) {
	if (shark[A].z > shark[B].z) return true;
	return false;
}

void initMap() {
	for (int i = 0; i < shark.size(); i++) {
		if (!shark[i].live) continue;
		int y = shark[i].r;
		int x = shark[i].c;

		map[y][x].clear();
	}
}

void killShark() {
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (map[i][j].size() >1) {
				sort(map[i][j].begin(), map[i][j].end(), compare);

				int liveIdx = map[i][j][0];

				for (int k = 1; k < map[i][j].size(); k++)
					shark[map[i][j][k]].live = false;
				map[i][j].clear();
				map[i][j].push_back(liveIdx);
			}
		}
	}
}

void moveShark(int n) {
	
	int cur_y = shark[n].r;
	int cur_x = shark[n].c;
	int dir = shark[n].d;
	int speed = shark[n].s;

	if (dir == 1 || dir == 2)
		speed = speed % (R * 2 - 2);
	else if (dir == 3 || dir == 4)
		speed = speed % (C * 2 - 2);

	for (int i = 0; i < speed; i++) {

		int ny = cur_y + dy[dir];
		int nx = cur_x + dx[dir];

		//out of range= => change direction and move back
		if (ny<1 || ny>R || nx<1 || nx>C) {

			switch (dir) {
			case 1: dir = 2; break;
			case 2: dir = 1; break;
			case 3: dir = 4; break;
			case 4: dir = 3; break;
			}

			ny = ny + dy[dir] * 2;
			nx = nx + dx[dir] * 2;
		}

		cur_y = ny;
		cur_x = nx;
	}
	//update shark condition (location & direction)
	shark[n].r = cur_y;
	shark[n].c = cur_x;
	shark[n].d = dir;

	map[cur_y][cur_x].push_back(n);
}

void solution() {
	initMap();
	for (int i = 0; i < shark.size(); i++) {
		if (!shark[i].live) continue;
		if (shark[i].s == 0) {
			map[shark[i].r][shark[i].c].push_back(i);
			continue;
		}
		moveShark(i);
	}
	killShark();
}

void fishing(int x) {
	for (int i = 1; i <= R; i++) {
		if (map[i][x].size() != 0) {
			int idx = map[i][x][0];
			sum += shark[idx].z;
			shark[idx].live = false;
			map[i][x].clear();
			break;
		}
	}
}

void input() {
	cin >> R >> C >> M;
	for (int i = 0; i < M; i++) {
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		shark.push_back({ r,c,s,d,z});
		map[r][c].push_back(i);
	}
}

int main() {
	input();

	for (int i = 1; i <= C-1; i++) {
		fishing(i);
		solution();
	}
	fishing(C);
	cout << sum << endl;
	return 0;
}