백준 17143 낚시왕

 풀었던 백준 문제들, 코테, 대회 문제들 이런 것 들 중에 꽤 기억에 남는 문제들이 이미 많이 밀려서 한동안 그 문제들 정리해야지 싶다.

 

 그 첫번째 문제가 이 낚시왕 문제이다. 아래는 링크~

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

17143번: 낚시왕

 사실 그렇게 기억에 남을 만한 문제는 아니지만 가장 최근에 푼거라서(심지어 어제).. ㅎㅎ 그리고 첫 게시물로 시험삼아 올리는 문제

 

 1. 접근

 구현문제 대부분은 2차원 벡터나 배열 쓰는 경우가 허다하고 이 board를 만드는 병에 걸려있어서 일단 만들고 들어갔다. 가장 큰 그림은 낚시왕이 상어 줍줍하면 상어들 이동시키고 잡혔거나 잡아 먹힌 상어가 아니라면 한마리 각각 움직여 주었다. 만약 이번 상어가 이동하려는 칸에 상어가 존재할 수가 있다. 없으면 땡큐지만.. 만약 그 상어가 이번 상어의 움직임 전에 이미 움직여서 그 자리에 갔다면 이 두 상어는 맞짱을 떠야하지만 만약 그 상어가 움직이기 전이라면 그 상어를 재귀를 통해 먼저 움직여주어야 한다. 

 또한 이동에서 당연히 100x100 사이즈에 상어 속력이 최대 1000인거 보고 상어 움직이는 걸 구현할 때 한칸 씩 하는 것 만큼 멍청한 짓은 없겠다 싶었다. 그리고 방향과 위치에 따라 일일이 구현해주기 너무 귀찮아서 획일화 과정을 했다. 만약 (0,3)에 위치하고 오른쪽을 가리키고 속도가 10이라 가정하면, 그 상어를 맨 왼쪽인 (0,0)에 옮겨준 후에 속도를 13으로 증가시켜주었다. 만약 왼쪽을 가리키고 있었다면 (0,0)에서 시작해서 (0,C-1)에 부딪히고 돌아온다고 가정하고 그만큼 속도를 증가시켜 주었다. 위 아래로 움직일 때 또한 마찬가지. 이렇게 획일화 하고 나면 한칸씩 움직이는 것 대신 R또는 C로 속도를 mod연산 해주고 나머지값 더해준다. 근데 벽 팅겨서 오는거 위치를 잘 잡아줘야 하는데 잘 안되어서 걍 한칸씩 옮겼다. 시간초과 안걸리길 바라면서..ㅋㅋ

 

2. 풀었냐?

 아니.. 상어 움직임 하나하나 다 확인하면서 까지 잘 움직이나 확인해 보았는데 세상 잘 움직이지만 틀렸습니다 1%도 안찍고 나오는거 보고 코드 수정할라 하니 뭐가 틀린질 알아야지... 이럴땐 그냥 코드 다 지워버리고 다른 방식으로 풀기로 했다.

 

3. 접근2

 접근 1에서 까다로웠던 점은 두 상어가 부딪힐 때였다. 사실 board를 이용한게 중간 과정 보기도 편하고 낚시왕이 상어 줍줍할때 편하고 상어 위치 표기하기 쉬워보였지만.. 문제는 한칸에 하나의 상어만 표현 가능하고 그러다보니 두 상어 위치가 겹칠 때 위에서 말한 것 처럼 그 위치에 있던 상어가 움직인 놈이냐 아니냐 거르고 재귀 돌리고 이게 어딘가 실수가 나기 딱 좋아 보여서 board를 포기하고 간단하게 두 개의 배열로 해결했다. 바로 상어 위치 배열과 상어 정보 배열. 두 배열 인덱스를 통해 각각 다른 배열에 접근 할 수 있다. 이렇게 하니 접근 1에서 사용한 상어 움직임을 그대로 사용하고 map<pair<int,int>, int> 로 서로 다른 상어가 pair<int,int> 로서 나타난 각 상어 위치를 겹치는 놈이 있느냐 없느냐를 판단하고 잡아먹을지 말지 value인 int에 상어 정보 배열 인덱스를 들고 있어서 잡아먹기 과정 처리. 게다가 이번 상어의 움직인 위치가 낚시왕이 줍줍할 라인에 서있다면 vector에 넣어서 줍줍과정을 조금이라도 빠르게 했다. vector 에 넣어서 하면 O(R*C)에서 O(R)로 줍줍 시간을 줄일 수 있으니..!!

#include<iostream>
#include<vector>
#include<map>
using namespace std;

typedef pair<int, int> P;
typedef pair<P, int> Pi;//speed, direc, size
vector<P> sharks;
vector<Pi>info;
int R, C, M;
int init(P cur, int direc) {
	int ret = 0;
	if (direc == 1) {
		ret += cur.first;
		ret += ((R - 1) - cur.first) * 2;
	}
	else if (direc == 4) {
		ret += cur.second;
		ret += ((C - 1) - cur.second) * 2;
	}
	else if (direc == 2) {
		ret += cur.first;
	}
	else
		ret += cur.second;
	return ret;
}

P move(int idx) {
	//print();
	int wall = 0, x, y;
	x = sharks[idx].first; y = sharks[idx].second;

	P delta = P(x, y);
	//cout << idx << " " << x << " " << y << endl;

	int cycle;
	int direc = info[idx].first.second;
	if (direc < 3) {//up&down
		//if(idx == 2) cout << "B direc : " << direc << endl;
		cycle = 2 * (R - 1);
		int start = init(P(x, y), direc);
		int next = start + info[idx].first.first;
		next %= cycle;
		int x = 0, a = 1;
		if (next > R - 1) {
			while (next--) {
				x += a;
				if (x == R - 1)
					a = -1;
			}
			delta.first = x;
			if (direc == 2)
				wall = 1;
		}
		else {
			delta.first = next;
			if (direc == 1)
				wall = 1;
		}
	}
	else {//left&right
		cycle = 2 * (C - 1);
		int start = init(P(x, y), direc);
		int next = start + info[idx].first.first;
		next %= cycle;
		int x = 0, a = 1;
		if (next > C - 1) {
			while (next--) {
				x += a;
				if (x == C - 1)
					a = -1;
			}
			delta.second = x;

			if (direc == 3)
				wall = 1;
		}
		else {
			delta.second = next;
			if (direc == 4)
				wall = 1;
		}
	}

	if (wall == 1) {
		if (info[idx].first.second < 3)
			info[idx].first.second = info[idx].first.second == 1 ? 2 : 1;
		else
			info[idx].first.second = info[idx].first.second == 3 ? 4 : 3;
	}

	if (delta.first == 0 && info[idx].first.second == 1)
		info[idx].first.second = 2;

	if (delta.second == 0 && info[idx].first.second == 4)
		info[idx].first.second = 3;

	return delta;
}
#include<queue>
int main() {

	cin >> R >> C >> M;
	sharks.resize(M);
	info.resize(M);
	vector<int> fishing;
	for (int i = 0; i < M; i++) {
		int x, y, s, d, z;
		cin >> x >> y >> s >> d >> z; x--; y--;
		sharks[i] = P(x, y);
		info[i] = Pi(P(s, d), z);
		if (y == 0)
			fishing.push_back(i);
	}
	int ret = 0;
	for (int cur = 0; cur < C; cur++) {
		map<P, int> mm;//x,y,idx
		if (fishing.size()) {
			int pivot = R + 1;
			int idx = -1;
			for (auto& e : fishing) {
				if (pivot > sharks[e].first && sharks[e].first != -1) {
					pivot = sharks[e].first;
					idx = e;
				}
			}
			sharks[idx] = P(-1, -1);
			ret += info[idx].second;
		}
		if (cur == C - 1)break;
		fishing.clear();
		for (int i = 0; i < M; i++) {
			if (sharks[i].first == -1)continue;
			P next = move(i);
			if (mm.count(next)) {
				if (info[mm[next]].second < info[i].second) {
					sharks[mm[next]] = P(-1, -1);
					mm[next] = i;
				}
				else {
					sharks[i] = P(-1, -1);
					continue;
				}
			}
			sharks[i] = next;
			mm[next] = i;
			if (cur + 1 == next.second)
				fishing.push_back(i);
		}
	}
	cout << ret << endl;
	return 0;
}

 4. 교훈

 구현문제 오래 걸려서 풀게 되면 (이 문제는 몇 년 걸렸다. 2021.12.31에 풀다가 연말 보내러 마무리 못하고 2022.1.1에 풀었으니 오래 걸렸지 뭐) 항상 다짐하는게 펜과 종이로 대강 구현 어케 할지 좀 쓰자~ 라는 건데 이번에도 다짐만 한거 같다. 아마 내일 한 문제 구현문제로 풀기로 하고 종이와 펜을 써보아요. 

 그리고 2차원 board를 사용하는 것을 다시 생각해 보기로 했다. 여지껏 구현 문제는 항상 board들고 풀었던 거 같은데 이번 문제를 계기로 어떤 문제들은 이 board를 아예 안써서 RuntimeErr : out of range <vector> 이거 볼때마다 열받았던 순간들을 경험하지 않게 되면 좋을 것 같다. 

 정리하자면 구현 문제 풀기 전에 스케치하기 그리고 이 스케치 할 때 이차원 배열 안써도 될 각을 꼭 보기!