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

서론

비교적 쉬운 시뮬레이션 문제.

그러나 구현은 오래걸린 문제.

아이디어

1. 지도 생성

먼저 지도를 만들어야한다. 각 상어의 정보를 상어가 위치한 칸에 입력시킨다.

이때 지도의 칸을 구조체 벡터로 만들어서 상어 정보를 입력시킨다.

구조체로 만드는 이유는 상어의 정보(s,d,z,moved)를 포함하기 위함이고(moved는 후술)

벡터로 만드는 이유는 각 칸에 여러마리의 상어가 들어갈 수 있도록 하기 위함이다. (같은 칸에 상어가 여러마리면 한마리만 살아남는데, 싸우기 직전 상황을 만들기 위함)

2. 낚시

강태공이 오른쪽으로 한칸 이동하면 그 열에서 가장 위의 상어를 먹는다.

상어가 있는지는 벡터.size()>0 을 이용하면 되고 있으면 출력변수에 z값을 더해주고 상어는 제거(pop)한다.

3. 상어 이동

지도의 모든 칸을 탐색해서 상어가 있으면 이동시킨다.

그리고 1번에서 상어의 정보가 담긴 구조체에 moved가 있다. 한번 이동한 상어가 다시 이동하는걸 방지하기 위함인데, 예를들어 0행부터 10행까지 상어가 있는지 탐색 도중에 1행의 상어가 4행으로 이동하면 4행을 탐색할때 이동했던 상어가 다시 탐색된다. 그래서 상어가 한번 이동하면 moved를 1로 바꿔준다. 모든 탐색이 끝나면 다시 0으로 바꿔줘야한다.

이동은 d의 방향으로 상어를 한칸씩 이동시킨다. 한칸 이동하면 s는 1 감소시키고 s가 0이 될때까지 반복한다. 그리고 벽을 만나면 방향을 바꾸고 한칸 이동시킨다.

4. 한마리만 살아남아야하는 상어들

이동 후 칸에 상어가 두마리 이상이면 발생한다.

해당 칸 벡터의 z를 기준으로 내림차순 정렬하고 벡터의 프론트만 살리고 나머지는 벡터에서 제거한다.

구현

//c++

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


typedef struct st {
	int z;
	int s;
	int d;
	int moved;
}st;

std::vector<st> map[102][102];
int sum;
int R, C, M;

bool compare(st a, st b) {
	if (a.z > b.z) return true;
	else return false;
}

void move(int y, int x) {
	int z = map[y][x][0].z;
	int s = map[y][x][0].s;
	int d = map[y][x][0].d;
	int cpS = s;
	
	map[y][x].erase(map[y][x].begin());

	//std::cout << y << " " << x <<" "<<d<< " -> ";
	while (s > 0) {
		if (d == 1) {
			if (y == 1) {
				d = 2;
				y = 2;
			}
			else y--;
		}
		else if (d == 2) {
			if (y == R) {
				d = 1;
				y = R-1;
			}
			else y++;
		}
		else if (d == 3) {
			if (x == C) {
				d = 4;
				x = C-1;
			}
			else x++;
		}
		else if (d == 4) {
			if (x == 1) {
				d = 3;
				x = 2;
			}
			else x--;
		}
		s--;
	}

	map[y][x].push_back({ z, cpS, d, 1});
	//std::cout << y << " " << x << " " << d<<std::endl;
}

int main() {
	std::cin >> R >> C >> M;

	// 지도 생성
	for (int i = 0; i < M; i++) {
		int r, c, s, d, z;
		std::cin >> r >> c >> s >> d >> z;
		map[r][c].push_back({ z,s,d,0}); // y, x, 속력, 방향, 크기
	}

	for (int i = 1; i <= C; i++) {
		// 낚시
		for (int j = 1; j <= R; j++) {
			if (map[j][i].size() > 0) {
				sum += map[j][i][0].z;
				map[j][i].pop_back();
				break;
			}
		}

		/*
		// 디버깅
		for (int j = 1; j <= R; j++) {
			for (int k = 1; k <= C; k++) {
				if (map[j][k].size() > 0) std::cout << j << " " << k << " " << std::endl;
			}
		}
		
		std::cout << std::endl;
		*/

		// 상어 이동
		for (int j = 1; j <= R; j++) {
			for (int k = 1; k <= C; k++) {
				if (map[j][k].size() > 0 && map[j][k][0].moved == 0) move(j, k);
			}
		}

		// 상어 전쟁
		for (int j = 1; j <= R; j++) {
			for (int k = 1; k <= C; k++) {
				if (map[j][k].size() > 1) {
					sort(map[j][k].begin(), map[j][k].end(), compare);
					int z = map[j][k][0].z;
					int s = map[j][k][0].s;
					int d = map[j][k][0].d;
					map[j][k].clear();
					map[j][k].push_back({ z, s, d, 0 });
				}
				else if (map[j][k].size() == 1) map[j][k][0].moved = 0;
			}
		}
		//std::cout << "-------" << std::endl;
	}

	std::cout << sum;

}