백준 17143 (낚시왕)

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

17143번: 낚시왕

간단한 구현 문제이다.

상어의 위치가 주어지며 격자판 안에 상어가 존재한다. 낚시꾼은 X축을 +1 하며 이동하면서 마지막 X축 까지 이동하면서 잡은 상어의 총크기를 구하면 되는 문제이다.

이때 주의해야 할 점이 있는데 상어가 이동할 수 있는 경우가 최대 1000 번이기 때문에 시간 초과를 주의해야 한다. 

TIP :

상어가 격자판의 Y or X 축을 한바퀴 돌아 제자리로 돌아오는 경우 몇 번 이동하는지 구하여 상어가 이동하는 횟수와 나누어 나머지 값을 취하면 다음과 같은 식이 성립한다. 

(상어가 한바퀴를 돌아 제자리로 돌아오기까지 걸리는 횟수) / (상어가 움직여야 하는 횟수)를 수행하여

만약 몫이 1 이상이라면 해당 상어는 몫에 해당하는 횟수만큼 본래의 자리를 들렷다 이동하기 때문에 몫에 해당하는 횟수의 연산을 없애고 나머지에 해당하는 횟수만큼 상어를 이동시키면 된다.

만약 몫이 1 보다 작다면 해당 상어는 한바퀴보다 덜 돌기 때문에 그냥 상어에게 주어진 회전 횟수만큼 연산을 수행하면 된다. 

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int check[4][2] = {
	-1, 0,
	+1, 0,
	0, +1,
	0, -1
};

struct Node{
	int y, x;
	int speed;
	int dir;
	int body;
	int name;
	int life;
};
vector<Node> sList;

int map[100][100];

int my, mx, m;

void move(){
	int n = sList.size();
	int overlap[100][100] = {0};

	for (int i = 0; i < n; ++i){
		Node now = sList[i];
		if (now.life == 1) continue;
		int sp;
		if (now.dir == 0 || now.dir == 1) sp = 2 * (my - 1);
		else if (now.dir == 2 || now.dir == 3)sp = 2 * (mx - 1);
		
        // 상어가 한바퀴 회전하여 제자리까지 돌아올 경우
		if (sp <= now.speed) sp = now.speed % sp;
        
        // 상어가 한바퀴 미만으로 이동할 경우
		else sp = now.speed;

		for (int j = 0; j < sp; ++j){
			int dy = now.y + check[now.dir][0];
			int dx = now.x + check[now.dir][1];
			if (dy >= 0 && dx >= 0 && dy < my && dx < mx){
				now.y = dy;
				now.x = dx;
			}
			else{
				if (now.dir == 0) now.dir = 1;
				else if (now.dir == 1) now.dir = 0;
				else if (now.dir == 2) now.dir = 3;
				else if (now.dir == 3) now.dir = 2;

				now.y = now.y + check[now.dir][0];
				now.x = now.x + check[now.dir][1];
			}
		}
        
		sList[i] = now;
        // 상어가 이동한 위치에 아무도 없을 경우
		if (overlap[now.y][now.x] == 0){
			overlap[now.y][now.x] = now.name;
		}
        // 상어가 이동한 위치에 누군가 있을경우 상어의 크기를 비교하여 선택
        // 없앨 상어는 life 에 check
		else{
			if (sList[overlap[now.y][now.x] - 1].body < now.body){
				sList[overlap[now.y][now.x] - 1].life = 1;
				overlap[now.y][now.x] = now.name;
			}
			else{
				sList[i].life = 1;
			}
		}
	}
	memcpy(map, overlap, 4 * 100 * 100);
}

int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> my >> mx >> m;
	int result = 0;
	int dy, dx, dir;
	Node tmp;

	for (int i = 0; i < m; ++i){
		cin >> dy >> dx >> tmp.speed >> dir >> tmp.body;
		tmp.y = dy - 1; 
		tmp.x = dx - 1;
		tmp.dir = dir - 1;
		tmp.name = i + 1;
		map[dy - 1][dx - 1] = i + 1;
		sList.push_back(tmp);
	}

	for (int x = 0; x < mx; ++x){
		for (int y = 0; y < my; ++y){
        // 해당 X축의 가장가까운 상어 삭제
			if (map[y][x] > 0){
				sList[map[y][x] - 1].life = 1;
				result += sList[map[y][x] - 1].body;
				break;
			}
		}
		move();
	}
	printf("%d", result);
	
}