(c++)백준 17143번: 낚시왕

www.acmicpc.net/problem/17143

17143번: 낚시왕

[풀이]

문제에 나온 규칙대로 구현하는 문제였다.

처음에 모든 상어를 각각의 s만큼 움직이게 해서 위치를 갱신해주었는데, 시간초과가 났다.

최악의 경우 10^3(상어 속력)*10^4(상어의 수)*10^2(C의 크기) = 10^9번의 연산을 하게 되므로 시간초과가 나게 된다!

상어가 위 아래로 움직일 땐 (R-1)*2, 좌우로 움직일 땐 (C-1)*2번 움직이면 같은 자리에 같은 방향을 가지고 돌아오게 된다.

이걸 이용하여 실제 움직이는 칸 수를 s%((R-1)*2)또는 s%((C-1)*2)로 하여 풀면 시간초과가 나지 않는다.

그리고 상어를 이동시킬 때 여러마리 상어의 위치가 섞이게 되므로 이미 움직인 상어를 표시하는 move 변수를 Shark구조체에 포함시켜야 했다.

 

※시간복잡도 계산 연습이 필요할 듯

 

#include <iostream>
#include <deque>
#include <algorithm>//sort
using namespace std;

struct Shark {
	int s, d, z;//속력,방향,크기
	int move;//움직였는지
};

bool sortShark(Shark &A, Shark &B) {
	return A.z > B.z;
}

int R, C, M;
deque<Shark>shark[101][101];//각 칸의 상어들 상태 저장
bool check[101][101];//상어가 있는 칸 체크
const int dx[] = { 0,-1,1,0,0 };//1:위, 2:아래
const int dy[] = { 0,0,0,1,-1 };//3:오른쪽, 4:왼쪽
int convert[] = { 0,2,1,4,3 };//방향 바뀔때 사용
int sum = 0;
int moveLabel = -1;


void Move(int x, int y, int s, int d, int z) {
	if (s == 0) {
		shark[x][y][0].move = -moveLabel;
		return;
	}
	int realMove = 0;
	if (d == 1 || d == 2) {
		//제자리에 같은 방향으로 돌아오는 경우 빼주기
		realMove = s % ((R - 1) * 2);
	}
	else
		realMove = s % ((C - 1) * 2);

	int nx = x;
	int ny = y;
	int nd = d;
	while (realMove--) {
		nx += dx[nd];
		ny += dy[nd];
		//경계 넘어가면 방향 전환
		if (nx <= 0 || nx > R || ny <= 0 || ny > C) {
			nx -= dx[nd];
			ny -= dy[nd];
			nd = convert[nd];
			nx += dx[nd];
			ny += dy[nd];
		}
	}
	
	shark[x][y].pop_front();
	shark[nx][ny].push_back({ s,nd,z,-moveLabel });
}

//상어이동
void moveShark() {
	//칸에 상어 있으면 이동
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (shark[i][j].empty())
				continue;
			if (shark[i][j][0].move == -moveLabel)
				continue;
			int s = shark[i][j][0].s;
			int d = shark[i][j][0].d;
			int z = shark[i][j][0].z;
			Move(i, j, s, d, z);
		}
	}
}

//상어 잡아먹기
void eatShark() {
	//상어가 두마리 있으면 큰 상어가 잡아먹기
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			int sharkcnt = shark[i][j].size();
			if (sharkcnt > 1) {
				sort(shark[i][j].begin(), shark[i][j].end(), sortShark);
				shark[i][j].erase(shark[i][j].begin() + 1, shark[i][j].end());
			}
		}
	}
}

void getShark() {
	//한 칸씩 이동하면서 상어잡기
	for (int col = 1; col <= C; col++) {
		for (int row = 1; row <= R; row++) {
			int sharkcnt = shark[row][col].size();
			//제일 가까운 상어 찾았으면
			if (sharkcnt > 0) {
				//cout << "r: " << row << ' ' <<  "c: " << col << '\n';
				//cout<< shark[row][col][0].z << '\n';
				sum += shark[row][col][0].z;
				shark[row][col].pop_back();
				break;
			}
		}
		moveShark();
		eatShark();
		moveLabel = -moveLabel;
	}
}

void solution() {
	cin >> R >> C >> M;
	for (int i = 0; i < M; i++) {
		int r, c, s, d, z;
		cin >> r >> c >> s >> d >> z;
		shark[r][c].push_back({ s,d,z,moveLabel });
	}
	getShark();
	cout << sum << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}