[C++] BOJ(백준) 17143 낚시왕

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

17143번: 낚시왕

 

구현 문제다.

 

마법사 상어와 파이어볼과 비슷한 문제다. https://abbiddo.tistory.com/19

 

큐나 벡터 하나만을 사용하면 이동한 상어에 대해 또 이동을 할 수 있다는 반례가 생긴다.

상어가 어디에 위치했는지 알기 위한 벡터와 현재 위치해 있는 상어들에 대한 정보를 담은 큐를 사용했다.

 

상어가 동일한 곳에 도착하면 큰 상어만 남아야 하는데 이동하자마자 큐에도 넣으면

상어가 상어를 먹을 때 큐에서 걸러낼 수가 없다.

그래서 상어 이동 시에는 위치 벡터에만 저장하고 상어를 먹을 때 큐에 넣는 작업을 동시에 진행했다.

 

이 문제에서 가장 까다로웠던 부분은 상어 이동이다.

반복문을 돌리지 않아도 되는 규칙을 찾았다.

 

5x6 크기이고 상어 위치가 1,1이며 아래로 움직인다고 가정하면

1	9		17		25
2	8	10	16	18	24
3	7	11	15	19	23
4	6	12	14	20	22
5		13		21

같은 형태로 나타낼 수 있다. 숫자는 이동 횟수(speed)다.

만약 3,1 에 위치하고 2칸 움직인다면 3+2 = 5로 5에 위치하게 된다.

 

규칙이 보이게 하기 위해서 (R-1) * 2의 나머지를 구하면 (여기서는 8로 나눈 나머지)

1	1		1		1
2	8	2	8	2	0
3	7	3	7	3	7
4	6	4	6	4	6
5		5		5

처럼 반복성을 나타낸다. 뒤에서 계산을 위해 0은 (R-1) * 2로 처리했다.

 

여기서의 규칙성을 찾으면, 1행부터 R헹까지 R과의 차의 절댓값이 동일하다.

4	4
3	3
2	2
1	1
0

맨 윗줄이 1행이므로 R에서 값을 빼주면 상어가 이동 후 위치한 행을 알 수 있다.

 

방향을 알기위해서는 상어의 현재 위치에 이동 값 s를 더한 후 - 2를 해준다.

거기에 (R-1)로 나눈 몫을 통해 방향을 알 수 있다.

(-2를 해주는 이유는 1번째 인덱스부터 시작하고, 시작점인 1은 예외적인 경우이기 때문이다.)

이 부분은 눈에 딱 보인 부분이라 자세한 설명이 어렵다.

나눈 몫이 홀수라면 방향을 바꾼다.

 

우측으로 가는 경우 R을 C로 변경해주면 된다.

 

위로 가는 경우와 좌측으로 가는 경우가 조금 까다로웠는데 마땅한 방법이 떠오르지 않아

처음 벽에 부딪히는 것만 계산해주어 아래와 우측으로 가는 방향으로 맞춰주었다.

그 후 아래와 우측으로 가는 것과 동일하게 진행했다.

 

그리고... 다 해냈다고 생각했는데 72%에서 도무지 넘어가질 않았다...

그 이유는 낚시왕이 상어를 잡을 때 상어의 좌표를 기록했는데(dr, dc) 그 좌표의 초기화를 반복문 밖에서 한 탓이었다...

 

해결하겠다고 애꿎은 상어 이동과 상어 먹기(정리) 코드만 들여다보고 엎었다.

상어 이동에서 간단해 보이는 방법이 있어 아래 함께 정리한다.

 

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

struct shark {
	int r, c, s, d, z;
};

vector<shark> bada[101][101];
queue<shark> q;

int main() {
	int R, C;	cin >> R >> C;
	int n;	cin >> n;
	int sum = 0;

	for (int i = 0; i < n; i++) {
		int a, b, c, d, e;	cin >> a >> b >> c >> d >> e;
		bada[a][b].push_back({ a,b,c,d,e });
		q.push({ a,b,c,d,e });
	}

	// 낚시왕 이동
	for (int T = 1; T <= C; T++) {
		int dc = -1, dr = -1;
		// 상어 잡기
		for (int i = 1; i <= R; i++) {
			if (bada[i][T].size() > 0) {
				sum += bada[i][T][0].z;
				bada[i][T].clear();
				dc = T;
				dr = i;
				break;
			}
		}

		// 상어 이동
		int qize = q.size();
		for (int i = 0; i < qize; i++) {
			int r = q.front().r;
			int c = q.front().c;
			int s = q.front().s;
			int d = q.front().d;
			int z = q.front().z;
			q.pop();

			// 상어가 잡혔으면 continue
			if (bada[r][c].size() == 0 || (dc == c && dr == r)) continue;

			// 상어 이동 전 자리는 비우기
			bada[r][c].erase(bada[r][c].begin());
			
			int dir;
			if (d == 1) {
				if (s < r) {
					r -= s;
					if (r == 1) d = 2;
				}
				else {
					dir = (R - r + s - 1) / (R - 1);
					if (dir % 2 == 1) d = 2;
					r = 2 + s - r;
					r %= ((R - 1) * 2);
					if (r == 0) r = (R - 1) * 2;
					r = abs(R - r);
					r = R - r;
					if (r == 1) d = 2;
					else if (r == R) d = 1;
				}
			}
			else if (d == 2) {
				r += s;
				dir = (r - 2) / (R - 1);
				if (dir % 2 == 1) d = 1;
				r %= ((R - 1) * 2);
				if (r == 0) r = (R - 1) * 2;
				r = abs(R - r);
				r = R - r;
				if (r == 1) d = 2;
				else if (r == R) d = 1;
			}
			else if (d == 3) {
				c += s;
				dir = (c - 2) / (C - 1);
				if (dir % 2 == 1) d = 4;
				c %= ((C - 1) * 2);
				if (c == 0) c = (C - 1) * 2;
				c = abs(C - c);
				c = C - c;
				if (c == 1) d = 3;
				else if (c == C) d = 4;
			}
			else {
				if (s < c) {
					c -= s;
					if (c == 1) d = 3;
				}
				else {
					dir = (C - c + s - 1) / (C - 1);
					if (dir % 2 == 1) d = 3;
					c = 2 + s - c;
					c %= ((C - 1) * 2);
					if (c == 0) c = (C - 1) * 2;
					c = abs(C - c);
					c = C - c;
					if (c == 1) d = 3;
					else if (c == C) d = 4;
				}
			}
			bada[r][c].push_back({ r,c,s,d,z });
		}

		// 상어 정리
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				// 벡터 사이즈가 1이면 바로 큐에 push
				if (bada[i][j].size() == 1) q.push(bada[i][j][0]);
				
				// 벡터 사이즈가 1보다 크면 상어 크기 최댓값 탐색
				else if (bada[i][j].size() > 1) {
					shark maxi = bada[i][j][0];
					int bize = bada[i][j].size();
					for (int k = 1; k < bize; k++)
						if (maxi.z < bada[i][j][k].z) maxi = bada[i][j][k];
					
					// 벡터 비워주고 최댓값 상어만 남기기
					bada[i][j].clear();
					bada[i][j].push_back(maxi);
					q.push(maxi);
				}
			}
		}
	}
	cout << sum;
}

 

// 상어 이동을 간단한 규칙만 찾아서 해결한 방법이다

			int rr = r, cc = c;

			// (R-1)*2만큼 움직이면 제자리에 도착. 즉, 나머지만큼만 움직이면 됨
			if (d == 1 || d == 2) s = s % ((R - 1) * 2);
			else s = s %( (C - 1) * 2);

			// 위에서 구한 나머지만큼 이동 반복
			for (int j = 0; j < s; j++) {
				rr += ddr[d];
				cc += ddc[d];

				// 범위 벗어나면
				if (rr < 1 || rr > R || cc < 1 || cc > C) {
					// 한 칸 되돌리고
					rr -= ddr[d];
					cc -= ddc[d];

					// 방향 바꾸고
					if (d % 2 == 1) d++;
					else d--;

					// 바꾼 방향으로 한 칸 이동
					rr += ddr[d];
					cc += ddc[d];
				}
			}
			bada[rr][cc].push_back({ rr,cc,s,d,z });

 

이 방법은 위에서 찾은 규칙 중 제자리에 돌아오는 것에 대한 계산을 스킵한 것이다.

총 이동 횟수에서 (R-1)*2 번마다 제자리에 돌아온다.

즉, 총 이동 횟수 % ((R-1) * 2) 만큼만 반복문으로 이동하면 위치를 찾을 수 있는 것이다.

* 이 방법을 사용하기 위해서는 

int ddr[5] = { 0, -1, 1, 0 ,0 };
int ddc[5] = { 0, 0, 0, 1, -1 };

배열 두 줄을 함께 선언해줘야 한다.

 

확실히 규칙을 찾고 찾아 반복문을 쓰지 않은 방법이 시간이 줄어들긴 한다.