[APS] 백준 17143. 낚시왕 C++ 풀이

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

17143번: 낚시왕

 

 

 Problem 

1. R×C 크기의 격자판에서 낚시왕이 상어 낚시를 한다. 칸에는 상어가 최대 한 마리 들어있을 수 있고, 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음 1번 열의 한 칸 왼쪽에 있다.
2. 1초 동안 아래에 적힌 일이 순서대로 일어난다.
   1) 낚시왕이 오른쪽으로 한 칸 이동한다.
   2) 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
   3) 상어가 방향과 속도에 따라 이동한다. 이 때, 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한 채로 이동한다. 한 칸에 상어가 여러 마리 존재하는 경우 가장 큰 상어만 남는다.
3. 낚시왕이 잡은 상어 크기의 합을 구한다.

 

 

 Solution 

문제에 그림 많고 시뮬레이션하는, 제가 좋아하는 유형의 문제라서 되게 재미있게 풀었습니다.

먼저, 각 상어의 위치, 속력, 방향, 크기를 가지고 있는 상어 구조체를 만들었습니다. 낚시터의 각 칸마다 상어를 넣습니다. (저는 pop, push 연산을 편하게 하려고 벡터를 사용했지만, 굳이 벡터를 사용하지 않아도 됩니다.. ㅎㅎ) 그 뒤는 문제에서 시키는 대로 구현해주면 되는데, 처음에는 상어의 위치를 바꿀 때 상어의 속력만큼 while문을 돌리면서 한 칸씩 이동하는 식으로 구현해서 시간 초과를 받았습니다. (낚시왕은 100번 이동 가능하고, 상어의 개수는 총 10000마리까지 가능한데, 속력인 s가 1000까지 가능하다보니 당연히 시간 초과..😂)

생각해보니 위, 아래 방향으로 움직이는 상어의 경우 속력이 (R - 1) * 2배일 때, 좌우로 움직이는 상어의 경우 속력이 (C - 1) * 2배 일 때 같은 자리의 똑같은 방향으로 돌아오게 됩니다. 따라서 처음 상어의 속력을 저장할 때 최소의 경우만 생각할 수 있도록 방향에 따라 (R - 1) * 2 또는 (C - 1) * 2로 나눈 나머지를 속력으로 저장해서 시간 초과 문제를 해결했습니다. 이 부분이 해당 문제를 푸는 키포인트겠네요.

정리하자면 아래와 같습니다.

 

1. 상어가 원래 자리로 돌아오는 경우를 제외하고 최소의 이동거리만 저장한다.
2. 낚시왕을 이동시키고 해당 거리에서 제일 가까운 거리의 상어를 잡은 뒤(pop_back) 답에 더해준다.
3. 벡터에 상어가 존재할 경우 pop해주고, 상어의 속력만큼 while문을 돌리면서 다음 위치를 찾는다.
4. 다음 위치에 상어가 있을 경우, 크기를 비교해서 현재 상어가 크기가 더 큰 경우 상어를 바꿔주고, 현재 상어가 더 작으면 현 상태를 유지한다. 상어가 없는 경우 현재 상어를 바로 넣는다.
5. 2~4 과정을 낚시왕이 열의 가장 끝 부분에 도착할 때까지 반복한다.

 

 

 Code 

	// https://www.acmicpc.net/problem/17143
	#include <iostream>
	#include <vector>
	using namespace std;
	const int dir[5][2] = { {0, 0}, {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
	struct Shark {
	int r, c, s, d, z;
	// 위치, 속력, 방향, 크기
	};
	int R, C, M; // 격자판 크기, 상어의 개수
	int Answer;
	vector<Shark> Sharks[102][102]; // [i][j] 위치에서의 상어
	bool in_range(int r, int c) {
	return 0 < r && r <= R && 0 < c && c <= C;
	}
	int change_dir(int d) {
	if (d == 1) return 2;
	if (d == 2) return 1;
	if (d == 3) return 4;
	if (d == 4) return 3;
	}
	int main() {
	cin >> R >> C >> M;
	for (int i = 0; i < M; i++) {
	int r, c, s, d, z;
	cin >> r >> c >> s >> d >> z;
	if (d == 1 || d == 2) s %= ((R - 1) * 2); // 상어가 원래 자리로 돌아오는 경우,
	if (d == 3 || d == 4) s %= ((C - 1) * 2); // 해당 부분은 빼고 최소 속도만 고려한다.
	Sharks[r][c].push_back({ r, c, s, d, z });
	}
	int K = 0;
	while (++K <= C) {
	// 1. 해당 열에서 제일 가까운 상어 잡기
	for (int i = 1; i <= R; i++) {
	if (!Sharks[i][K].empty()) {
	Answer += Sharks[i][K][0].z;
	Sharks[i][K].pop_back();
	break;
	}
	}
	vector<Shark> newSharks[102][102]; // 중복 이동을 방지하기 위해 새로운 상어를 저장
	// 2. 상어 이동
	for (int i = 1; i <= R; i++) {
	for (int j = 1; j <= C; j++) {
	if (Sharks[i][j].empty()) continue;
	Shark currShark = Sharks[i][j][0];
	Sharks[i][j].pop_back();
	int& cr = currShark.r;
	int& cc = currShark.c;
	int cs = currShark.s;
	int& cd = currShark.d;
	while (cs--) {
	int nr = cr + dir[cd][0];
	int nc = cc + dir[cd][1];
	if (!in_range(nr, nc)) {
	cd = change_dir(cd);
	}
	cr += dir[cd][0];
	cc += dir[cd][1];
	}
	// 3. 상어가 있을 경우 큰거 하나만 남기기
	if (!newSharks[cr][cc].empty()) {
	if (newSharks[cr][cc][0].z < currShark.z) {
	newSharks[cr][cc].pop_back();
	newSharks[cr][cc].push_back(currShark);
	}
	}
	// 상어가 없으면 바로 push
	else newSharks[cr][cc].push_back(currShark);
	}
	}
	// 새로운 상어를 기존 상어 배열에 복사
	for (int i = 1; i <= R; i++) {
	for (int j = 1; j <= C; j++) {
	Sharks[i][j] = newSharks[i][j];
	}
	}
	}
	cout << Answer << endl;
	return 0;
	}

view raw B17143.cpp hosted with ❤ by GitHub