문제

문제 링크

해설

• 어려운 시뮬레이션(구현) 문제입니다. 문제를 정리해봅시다.
  1. 낚시왕이 오른쪽으로 한 칸 이동합니다.
  2. 낚시왕이 있는 열에서 가장 가까운 행에 있는 상어를 잡습니다.
  3. 모든 상어가 규칙에 맞게 이동합니다.
• 우선, 모든 상어가 좌표(y, x)와 속도, 방향, 크기 정보를 갖고 있기 때문에 간단한 구조체 struct Shark { int y, x, s, d, z, death; }를 하나 만드는 것이 좋겠습니다. 이때, 낚시왕에게 잡힌 상어는 죽고, 상어가 겹쳤을 때 어느 한 상어는 죽기 때문에 death라는 멤버 변수를 하나 추가로 뒀습니다.
  
• 둘째, R x C 격자판은 최대 100 x 100이며, 최대 속도 1,000까지 가질 수 있는 상어가 최대 10,000마리가 있을 수 있습니다. 그러므로 각 상어를 움직이는 단계에서 단순 for문으로 한 칸씩 이동하는 방법은 굉장히 시간이 오래 걸려서 시간초과 가능성이 있습니다.
  • 저희는 굳이 상어를 한 칸씩 옮길 필요가 없습니다. 그저 최종적으로 해당 상어가 어느 위치로 이동하는지가 궁금할 뿐입니다.
  • 따라서, 모듈라 연산으로 양쪽 벽을 찍고 다시 제자리로 돌아오는 경우, 즉, 가로 이동인 경우 2 * (C - 1), 세로 이동인 경우 2 * (R - 1)로 모듈라 연산을 하면, 이동 숫자를 최소한으로 줄일 수 있습니다.
• 셋째, 방향을 전환할 때, 위는 아래로, 왼쪽은 오른쪽으로 반대로 바꿔야 합니다.
  • 이 연산은 XOR 연산으로 쉽게 할 수 있습니다.
  • 0(00) ^ (01) = (01) = 1 (0 -> 1)
  • 1(01) ^ (01) = (00) = 0 (1 -> 0)
  • 2(10) ^ (01) = (11) = 3 (2 -> 3)
  • 3(11) ^ (01) = (10) = 2 (3 -> 2)
    
  • 따라서 d ^= 1 수식으로 방향을 반대로 전환할 수 있습니다.
• 넷째, 문제에선 드러나지 않지만 이 문제 또한 동시성 문제가 있습니다.
  • 즉, 각 상어는 1초에 한 번에 동시에 움직이기 때문에, 각 상어가 움직이는 결과를 원본에 적용해서는 안 됩니다.
  • 각 상어가 움직이결과는 다른 곳에다가 저장한 뒤, 모든 상어가 이동이 끝난 뒤 결과를 원본에 적용는 하는 방식으로 해야만 동시성 문제를 해결할 수 있습니다.
• 위 4가지 사항을 주의하면서 코드를 아래와 같이 작성하면, 문제를 해결할 수 있습니다. 어려운 구현문제였습니다.

코드

#include <bits/stdc++.h>
using namespace std;

constexpr int dy[4] = {-1, 1, 0, 0};
constexpr int dx[4] = {0, 0, 1, -1};
struct Shark { int y, x, s, d, z, death; } s[10'000];

int R, C, M, arr[100][100], temp[100][100];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> R >> C >> M;
	for (int i = 1; i <= M; ++i) {
		cin >> s[i].y >> s[i].x >> s[i].s >> s[i].d >> s[i].z;
		s[i].y--; s[i].x--; s[i].d--;
		s[i].s %= ((s[i].d <= 1) ? 2 * (R - 1) : 2 * (C - 1));
		arr[s[i].y][s[i].x] = i;
	}
	int ans = 0;
	for (int king = 0; king < C; ++king) {
		// 1. Get shark
		for (int y = 0; y < R; ++y) {
			if (arr[y][king] == 0) continue;
			ans += s[arr[y][king]].z;
			s[arr[y][king]].death = 1;
			arr[y][king] = 0;
			break;
		}
		// 2. Shark moves
		memset(temp, 0, sizeof(temp));
		for (int i = 1; i <= M; ++i) {
			if (s[i].death) continue;
			int y = s[i].y, x = s[i].x, d = s[i].d, dist = s[i].s;
			int ny, nx;
			while (true) {
				ny = y + dist * dy[d], nx = x + dist * dx[d];
				if (0 <= ny && ny < R && 0 <= nx && nx < C) break;
				if (d <= 1) {	// Up & Down
					if (ny < 0) {
						dist -= y;
						y = 0;	
					} else {
						dist -= R - 1 - y;
						y = R - 1;
					}
				} else {		// Left & Right
					if (nx < 0) {
						dist -= x;
						x = 0;
					} else {
						dist -= C - 1 - x;
						x = C - 1;
					}
				}
				d ^= 1;	// Reverse direction
			}
			// 3. If next position is empty / Or there is already sharks,
			if (temp[ny][nx] == 0) temp[ny][nx] = i;
			else {
				if (s[temp[ny][nx]].z > s[i].z) s[i].death = 1;
				else {
					s[temp[ny][nx]].death = 1;
					temp[ny][nx] = i;
				}
			}
			// 4. Change shark's position and direction.
			s[i].y = ny;	s[i].x = nx;	s[i].d = d;
		}
		memcpy(arr, temp, sizeof(temp));	// temp -> arr (동시성문제 해결)
	}
	cout << ans;
}

소스코드 링크

결과