[C++] 백준 17143번: 낚시왕

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

17143번: 낚시왕

 

 - 풀이

 구현해야할 것은 크게 2가지다. 한 줄에서 가장 위에 있는 상어를 잡는 catchShark()와, 상어들을 이동시키는 moveSharks() 함수이다. 전자는 매우 간단하게 구현이 가능하다. 하지만 문제는 후자이다.

 

 moveSharks() 함수는 모든 살아있는 상어들을 반복문으로 돌면서, 각각의 위치와 속도, 그리고 방향에 따라 nextPosition을 구해준다. 다음 좌표를 구해주는 함수는 getNextPosition()으로 구현하였다. 사실상 이 함수가 이 문제의 핵심이다.

 우선 speed를 (해당 축의 길이) - 1로 나눈 나머지로 치환할 수 있다. 가령 예제 입력 1에서 축의 길이가 4인 x축에서의 상황에서, 7번을 이동하면 위치와 방향이 그대로인 채로 남아있기 때문에 이것이 가능하다. 다음으로 이것을 통한 다음 좌표를 구하는 로직이 있는데, 사실 이것은 직접 여러 값들을 테스트해보면서 도출해낸 일반화된 코드이기 때문에 어떻게 설명해낼 방도가 없는 듯 하다.. 그나마 언급할 수 있는 부분은, '길게 이동하여 방향이 2번 바뀌었을 경우', '적당히 이동하여 방향이 1번 바뀌었을 경우', '짧게 이동하여 방향이 바뀌지 않았을 경우'를 나누었다는 것이다. 또한 위 3개의 경우가, offset이 음수인지 양수인지 여부에 따라 갈리기 때문에 총 6개의 경우로 나뉜다.

 getNextPosition()의 구현이 힘들다면, 단순히 1칸씩 이동하는 것을 speed(정확히는 이것을 (축의 길이 - 1)만큼 나눈 나머지)만큼 행하는 로직을 구현하여 반복문을 돌려도 되는 것으로 보인다. 다만 코드와 로직이 깔끔해보일지언정 비효율적인 방법이라는 한계가 있다.

 다시 돌아와서, 이제 다음 좌표를 구할 수 있으므로 이제, 'nextMap'을 작성한다. nextMap은 말그대로 모든 상어가 이동한 뒤의 결과 맵이며 함수 마지막 부분에서 이것을 map으로 deepcopy할 예정이다. 이렇게 해주는 이유는 상어의 위치가 중복될 때 데이터를 처리해주는 것이 매우 번거롭기 때문이다.(상어의 위치가 중복되는 경우를 생각해보라. 크기 비교를 통한 삭제를 할 때 아직 이동하지 않은 상어라면 유효하지 않을 것이다. 또한 이 경우를 처리하더라도 이전 상어들의 인덱스 뿐만 아니라 이동 여부까지 저장해야 겨우 일반화가 가능할 것이다.)

 

 개인적으로는, map, nextMap, moveShark()와 관련된 중복 처리 및 상어의 isAlive 상태 처리를 깔끔하게 하는 것이 어려웠다,

 

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

struct Shark {
	bool isAlive;
	int x, y;
	int speed;
	int dir;
	int size;
};

int R, C;
vector<Shark> sharks;
int map[101][101]; // sharks의 인덱스들 저장
int nextMap[101][101];  

// 상 하 우 좌
int dx[5] = { 0, -1, 1, 0, 0 };
int dy[5] = { 0, 0, 0, 1, -1};

int catchShark(int y) {
	int res = 0;

	int i;
	for (i = 1; i < R+1; i++) {
		if (map[i][y] != 0 && sharks[map[i][y]].isAlive) {
			res = sharks[map[i][y]].size;
			sharks[map[i][y]].isAlive = false;
			map[i][y] = 0;
			break;
		}
	}

	return res;
}

pair<int, int> getNextPosition(int index, int x, int y) {
	// 상, 하
	if (sharks[index].dir <= 2) {
		// Set nx
		int offsetX = (dx[sharks[index].dir] * (sharks[index].speed % (2 * (R - 1))));
		int nx = x + offsetX;
		if (offsetX >= 0) {
			if (nx >= 2 * R - 1) nx -= 2 * (R - 1);
			else if (nx >= R) {
				if (sharks[index].dir % 2 == 0) sharks[index].dir--;
				else sharks[index].dir++;
				nx = 2 * R - nx;
			}
		}
		else {
			if (nx <= -R + 2) nx += 2 * (R - 1);
			else if (nx <= 1) {
				if (sharks[index].dir % 2 == 0) sharks[index].dir--;
				else sharks[index].dir++;
				nx = 2 - nx;
			}
		}

		return { nx, y };
	}
	// 좌, 우
	else {
		// Set ny
		int offsetY = (dy[sharks[index].dir] * (sharks[index].speed % (2 * (C - 1))));
		int ny = y + offsetY;

		if (offsetY >= 0) {
			if (ny >= 2 * C - 1) ny -= 2 * (C - 1);
			else if (ny >= C) {
				if (sharks[index].dir % 2 == 0) sharks[index].dir--;
				else sharks[index].dir++;
				ny = 2 * C - ny;
			}
		}
		else {
			if (ny <= -C + 2) ny += 2 * (C - 1);
			else if (ny <= 1) {
				if (sharks[index].dir % 2 == 0) sharks[index].dir--;
				else sharks[index].dir++;
				ny = 2 - ny;
			}
		}

		return { x, ny };
	}
}

void moveShark(int x, int y, int nx, int ny) {
	// 중복 X
	if (nextMap[nx][ny] == 0)
		nextMap[nx][ny] = map[x][y];
	// 위치가 겹치면서 현재 이동할 상어가 더 큰 경우
	else if (sharks[map[x][y]].size > sharks[nextMap[nx][ny]].size) {
		sharks[nextMap[nx][ny]].isAlive = false;
		nextMap[nx][ny] = map[x][y];
	}
	// 위치가 겹치지만 현재 이동할 상어가 더 작은 경우
	else
		sharks[map[x][y]].isAlive = false;
}

void moveSharks() {
	int i, j;

	// Init nextMap
	for (i = 1; i < R + 1; i++) {
		for (j = 1; j < C + 1; j++) nextMap[i][j] = 0;
	}

	// Set nextMap depending on sharks
	for (i = 1; i < sharks.size(); i++) {
		if (!sharks[i].isAlive) continue;

		int x = sharks[i].x;
		int y = sharks[i].y;

		pair<int, int> nextPos = getNextPosition(i, x, y);
		int nx = nextPos.first;
		int ny = nextPos.second;

		sharks[i].x = nx;
		sharks[i].y = ny;

		moveShark(x, y, nx, ny);
	}

	// Deepcopy: map <- nextMap
	for (i = 1; i < R + 1; i++) {
		for (j = 1; j < C + 1; j++) map[i][j] = nextMap[i][j];
	}
}

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

	int M;
	cin >> R >> C >> M;

	sharks.push_back(Shark());
	int i, j;

	// Init map
	for (i = 1; i < R + 1; i++) {
		for (j = 1; j < C + 1; j++) map[i][j] = 0;
	}

	for (i = 0; i < M; i++) {
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;

		Shark sh;
		sh.isAlive = true;  sh.x = r; sh.y = c;
		sh.speed = s; sh.dir = d; sh.size = z;
		sharks.push_back(sh);

		map[r][c] = sharks.size() - 1;
	}

	// Solution
	int res = 0;
	for (j = 1; j < C+1; j++) {
		res += catchShark(j);
		moveSharks();
	}
	cout << res;
}