C++:: boj 17143 < 낚시왕 >

문제만 보면 크게 어렵지 않지만 상어가 왔다 갔다 하는 부분을 구현하는 데 시간을 좀 쓴 문제이다. 수식으로 만들어서 풀려하였지만 단순히 직접 이동하는 방법을 사용하였고, 이때 일정 거리 이상이면 반복되는 구간이 존재하므로 최적화를 해줄 수 있다.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int R, C, M;
int r, c, s, d, z, answer;
int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, 1, -1}, change_dir[5] = {0, 2, 1, 4, 3};

int main() {
	cin >> R >> C >> M;
	vector<vector<int>> board(R, vector<int>(C, 0)), moved(R, vector<int>(C));
	unordered_map<int, vector<int>> um;
	for (int i=1; i<=M; i++) {
		cin >> r >> c >> s >> d >> z;
		board[r-1][c-1] = i;// 상어 번호로 표기
		um[i] = {s, d, z};// 상어 정보 저장
	}
	for (int j=0; j<C; j++) {
		// 잡고
		for (int i=0; i<R; i++) {// 상어 잡기
			if (board[i][j]) {
				answer += um[board[i][j]][2];
				um.erase(board[i][j]);
				board[i][j] = 0;
				break;
			}
		}
		// 이동
		for (auto& r : moved) fill(r.begin(), r.end(), 0);
		for (int i=0; i<R; i++) {
			for (int j=0; j<C; j++) {
				int shark = board[i][j];
				if (shark) {
					int speed = um[shark][0], dir = um[shark][1];
					int x = i, y = j;
					speed %= dir <= 2 ? (R-1)*2 : (C-1)*2;// (행렬의 길이-1)*2 번째마다 반복이 되므로 나머지를 사용한다.
					while (speed--) {
						int nx = x + dx[dir], ny = y + dy[dir];
						if (nx<0 || ny<0 || nx>=R || ny>=C) {
							dir = change_dir[dir];
							nx = x + dx[dir];
							ny = y + dy[dir];
						}
						x = nx;
						y = ny;
					}
					if (moved[x][y] && um[shark][2] < um[moved[x][y]][2]) continue;// 같은 공간에 상어가 이미 있고 현재 상어가 사이즈가 작으면 잡아 먹힌다.
					moved[x][y] = shark;
					um[shark][1] = dir;
				}
			}
		}
		board = moved;
	}
	cout << answer << "\n";
}