[G1] 백준 17143번 낚시왕 C++ 구현, 시뮬레이션, 우선순위 큐

리뷰

 

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

상어가 다른 상어를 잡아먹으면 잡아먹은 상어만큼 몸집이 커지는 줄 알았다...

오히려 더 어렵게 생각해서 한번 Fail을 받은 문제

 

 

전역 변수

• r : 맵의 세로 길이를 저장할 변수
• c : 맵의 가로 길이를 저장할 변수
• m : 상어의 개수를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 맵 정보를 저장하기 위한 정수형 2차 배열
• dx, dy : 4방향 탐색을 하기 위한 방햘 배열
• Shark : 상어의 정보를 정의한 구조체, 상어의 번호 index, 위치 x, y, 속도 s, 방향 d, 크기 z를 저장하고, 상어의 크기 z를 기준으로 내림차순 정렬하는 비교 함수를 갖는다.
• sharks : 상어의 정보를 저장할 Shark타입의 배열

 

함수

1. input

void input()

 

맵과 상어 정보를 입력 받기 위한 함수

1. r, c, m을 입력 받고, 1부터 m까지 for문을 개행해 준다.
2. 1~m번의 상어 정보를 입력 받아 맵 상에 인덱스를 배치하고 sharks배열을 초기화 해준다.
3. 이때 방향 배열은 -1만큼 감소시켜 0-based-indexing을 해주었다, 근데 딱히 필요 없는듯?

 

2. solution

void solution()

 

낚시왕을 이동시키며 문제에서 주어진 1, 2, 3번 로직을 수행하는 함수

1. col을 0으로 초기화 해주고, col을 후위 증가 시켜주면서 c보다 작을 경우 while문을 수행한다.
2. row를 0으로 초기화 해주고, row를 후위 증가 시켜주면서 r보다 작을 경우 while문을 수행한다.
3. 맵 상에서 상어를 만난 경우 그 상어의 크기만큼 ans에 더해준 뒤 맵에서 0으로 바꿔주고 break 처리한다.
4. Shark타입의 우선순위 큐 pq를 초기화 하고 r * c크기의 맵 정보를 순회한다.
5. 상어를 만난 경우 맵 상에서 0으로 변경해 준 후 move함수를 통해 상어를 이동시켜 준다.
6. 이동시킨 상어 정보를 최신화 해준 뒤 pq에 삽입해 준다.
7. pq가 빌 때 까지 while루프를 개행하고, 매 루프마다 상어를 한개씩 꺼내어 준다.
8. 이동 후 좌표에 상어가 이미 존재할 경우 continue처리를, 비어있다면 상어의 인덱스를 맵에 배치해 준다.

 

3. Move

Shark move(Shark& shark)

 

상어가 움직이는 시뮬레이션을 진행할 함수

1. 매개변수로 Shark타입의 상어 정보 shark를 참조로 받아준다.
2. shark의 방향이 상하, 좌우인 경우를 나누어서 이동시켜 준다.
3. 상하 이동인 경우 변수 remain에 상어의 속도를 맵의 세로크기 - 1의 2배를 해준 값으로 나눈 나머지를 저장한다.
4. 정수형 cx에 상어의 현재 x좌표 위치를 저장해 준다.
5. remain만큼 while루프를 수행하고, cx가 1이라면 방향을 1로, cx가 r이라면 방향을 0으로 바꿔준다.
6. 현재 상어의 방향으로 이동을 수행해 준다.
7. 최종적으로 cx좌표를 상어의 x좌표로 갱신해 준 뒤 shark를 리턴해 준다.
8. 좌우 이동인 경우도 위와 로직이 같으며 방향 배열, cy, 맵의 가로길이를 참조해 로직을 구성했다.

 

4. print

void print(int fisher)

 

시뮬레이션을 디버깅 하기 위한 함수

1. 매개변수로 현재 낚시왕이 있는 열의 위치 fisher를 전달받는다.
2. (r + 1) * c 크기의 for문을 개행해 준다.
3. i가 0이면서 j가 fisher라면 F를 출력해 준 뒤 continue처리해 준다.
4. 아니라면 맵의 정보를 출력해 준다.
5. 출력 후 fisher를 한번 더 출력하여 진행 후 몇 초가 지났는지를 명시해 준다.

 

문제풀이

1. input함수를 통해 맵과 상어 정보를 입력 받아준다.
2. solution함수를 통해 낚시왕이 이동하면서 물고기를 잡고, 물고기의 이동을 시뮬레이션 해준다.
3. ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

1. 상어가 다른 상어를 잡아먹은 경우 잡아 먹은 상어의 크기만큼 더 커지는 것으로 이해했다.
2. 상어의 크기를 커지게 하는 로직을 삭제하고 continue처리로 변경해 주었더니 AC를 받았다.

 

참고 사항

• 상어의 속도가 최대 1000이므로 이동하는 횟수를 적당히 줄여줄 수록 시간의 영향을 덜 받을 듯 하다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int r, c, m, ans;
int lst[101][101];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Shark {
	int index, x, y, s, d, z;
	bool operator<(const Shark& other) const {
		return z < other.z;
	}
};
Shark sharks[10001];

void input() {
	cin >> r >> c >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y, s, d, z; cin >> x >> y >> s >> d >> z;
		lst[x][y] = i;
		sharks[i] = { i, x, y, s, d - 1, z };
	}
}

Shark move(Shark& shark) {
	if (shark.d == 0 || shark.d == 1) {
		int remain = shark.s % ((r - 1) * 2);
		int cx = shark.x;
		while (remain--) {
			if (cx == 1) shark.d = 1;
			else if (cx == r) shark.d = 0;
			cx += dx[shark.d];
		}
		shark.x = cx;
		return shark;
	}
	if (shark.d == 2 || shark.d == 3) {
		int remain = shark.s % ((c - 1) * 2);
		int cy = shark.y;
		while (remain--) {
			if (cy == 1) shark.d = 2;
			else if (cy == c) shark.d = 3;
			cy += dy[shark.d];
		}
		shark.y = cy;
		return shark;
	}
}

void print(int fisher) {
	for (int i = 0; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			if (i == 0 && j == fisher) {
				cout << 'F' << " ";
				continue;
			}
			cout << lst[i][j] << " ";
		}
		cout << "\n";
	}
	cout << fisher << "\n";
}

void solution() {
	int col = 0;
	while (col++ < c) {
		//print(col);
		int row = 0;
		while (row++ < r) {
			if (lst[row][col]) {
				ans += sharks[lst[row][col]].z;
				lst[row][col] = 0;
				break;
			}
		}
		priority_queue<Shark> pq;
		for (int i = 1; i <= r; ++i) {
			for (int j = 1; j <= c; ++j) {
				if (lst[i][j]) {
					Shark& shark = sharks[lst[i][j]];
					lst[i][j] = 0;
					Shark moved_shark = move(shark);
					sharks[moved_shark.index] = moved_shark;
					pq.push(sharks[moved_shark.index]);
				}
			}
		}
		while (!pq.empty()) {
			Shark shark = pq.top(); pq.pop();
			if (lst[shark.x][shark.y]) continue;
			else lst[shark.x][shark.y] = shark.index;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	input();
	solution();
	cout << ans;
}