백준 17143번 : 낚시왕

sol : 62' 53''

• 수행 시간 : 252ms
• 메모리 : 2340KB

Learnings

• 수행 시간을 어떻게 더 줄일 수 있을까?

1. temp grid 필요 X ... 252ms -> 192ms
2. shark move에서 시간 대폭 줄일 수 있을 것 같다.
   -> 192ms -> 32ms

before refactoring

#include <iostream>
#include <vector>

using namespace std;

#define MAX_R 101
#define MAX_C 101
#define EMPTY 0

#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4

int r, c, m;
// 상, 하, 우, 좌
const int ds[5][2] = { { 0, 0 }, { -1, 0 }, {1, 0}, { 0, 1 }, {0, -1} };
int grid[MAX_R][MAX_C];
int tempGrid[MAX_R][MAX_C];
int score;

struct Shark {
	int r;
	int c;
	// speed
	int s;
	// direction
	int d;
	// size
	int z;
	bool removed;

	Shark() {}
	Shark(int _r, int _c, int _s, int _d, int _z) :
		r(_r), c(_c), s(_s), d(_d), z(_z), removed(false) { }
};

vector<Shark> sharks;

void Debug() {
	cout << endl << "DEBUG TEMP" << endl;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cout << grid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG TEMP FIN" << endl;
}

void Init() {
	cin >> r >> c >> m;

	sharks.resize(m + 1);
	for (int i = 1; i <= m; i++) {
		int _r, _c, s, d, z;
		cin >> _r >> _c >> s >> d >> z;

		sharks[i] = Shark(_r, _c, s, d, z);
		grid[_r][_c] = i;
	}
}

void Fishing(int row) {
	for (int i = 1; i <= r; i++) {
		if (grid[i][row] != EMPTY) {
			sharks[grid[i][row]].removed = true;
			score += sharks[grid[i][row]].z;
			grid[i][row] = EMPTY;
			return;
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= r && 1 <= j && j <= c;
}

void InitTempGrid() {
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			tempGrid[i][j] = EMPTY;
		}
	}
}

void DupGrid(int from[MAX_R][MAX_C], int to[MAX_R][MAX_C]) {
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			to[i][j] = from[i][j];
		}
	}
}

int Oppos(int d) {
	if (d == UP) return DOWN;
	if (d == DOWN) return UP;
	if (d == LEFT) return RIGHT;
	if (d == RIGHT) return LEFT;

	return -1;
}

void SharkMove() {
	InitTempGrid();

	for (int s = 1; s <= m; s++) {
		if (sharks[s].removed) continue;

		int ci = sharks[s].r, cj = sharks[s].c, cd = sharks[s].d;
		int cs = sharks[s].s;
		int ni = ci, nj = cj, nd = cd;

		if (cd == LEFT || cd == RIGHT) {
			cs = cs % ((c - 1) << 1);
			ni = ci;
			for (int dist = 1; dist <= cs; dist++) {
				nj += ds[nd][1];
				if (!InGrid(ni, nj)) {
					nd = Oppos(nd);
					nj += ds[nd][1] * 2;
				}
			}
		}
		else {
			cs = cs % ((r - 1) << 1);
			nj = cj;
			for (int dist = 1; dist <= cs; dist++) {
				ni += ds[nd][0];
				if (!InGrid(ni, nj)) {
					nd = Oppos(nd);
					ni += ds[nd][0] * 2;
				}
			}
		}

		if (tempGrid[ni][nj] != EMPTY) {
			int defendS = tempGrid[ni][nj];
			if (sharks[defendS].z > sharks[s].z) {
				sharks[s].removed = true;
			}
			else {
				sharks[defendS].removed = true;
				tempGrid[ni][nj] = s;
				sharks[s].r = ni, sharks[s].c = nj, sharks[s].d = nd;
			}
		}
		else {
			tempGrid[ni][nj] = s;
			sharks[s].r = ni, sharks[s].c = nj, sharks[s].d = nd;
		}
	}

	DupGrid(tempGrid, grid);
}

int main() {
	Init();

	for (int row = 1; row <= c; row++) {
		Fishing(row);

		SharkMove();
	}

	cout << score;

	return 0;
}

After refactoring

#include <iostream>
#include <vector>

using namespace std;

#define MAX_R 101
#define MAX_C 101
#define EMPTY 0

#define UP 1
#define DOWN 2
#define RIGHT 3
#define LEFT 4

int r, c, m;
// 상, 하, 우, 좌
const int ds[5][2] = { { 0, 0 }, { -1, 0 }, {1, 0}, { 0, 1 }, {0, -1} };
int grid[MAX_R][MAX_C];
int tempGrid[MAX_R][MAX_C];
int score;

struct Shark {
	int r;
	int c;
	// speed
	int s;
	// direction
	int d;
	// size
	int z;
	bool removed;

	Shark() {}
	Shark(int _r, int _c, int _s, int _d, int _z) :
		r(_r), c(_c), s(_s), d(_d), z(_z), removed(false) { }
};

vector<Shark> sharks;

void Init() {
	cin >> r >> c >> m;

	sharks.resize(m + 1);
	for (int i = 1; i <= m; i++) {
		int _r, _c, s, d, z;
		cin >> _r >> _c >> s >> d >> z;

		sharks[i] = Shark(_r, _c, s, d, z);
		grid[_r][_c] = i;
	}
}

void Debug() {
	cout << endl << endl;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cout << grid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
}

void Fishing(int row) {
	for (int i = 1; i <= r; i++) {
		if (grid[i][row] != EMPTY) {
			sharks[grid[i][row]].removed = true;
			score += sharks[grid[i][row]].z;
			grid[i][row] = EMPTY;
			return;
		}
	}
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= r && 1 <= j && j <= c;
}

void InitGrid() {
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			grid[i][j] = EMPTY;
		}
	}
}

int Oppos(int d) {
	if (d == UP) return DOWN;
	if (d == DOWN) return UP;
	if (d == LEFT) return RIGHT;
	if (d == RIGHT) return LEFT;

	return -1;
}

pair<int, int> MoveVertical(int pos, int dir, int speed) {
	if (r == 1) return { 1, dir };

	int cycle = 2 * (r - 1);
	speed %= cycle;

	int x;
	if (dir == DOWN) x = pos - 1;
	else x = cycle - (pos - 1);

	int nx = (x + speed) % cycle;

	if (nx < r) return { nx + 1, DOWN };
	else return { cycle - nx + 1, UP };
}

pair<int, int> MoveHorizontal(int pos, int dir, int speed) {
	if (c == 1) return { 1, dir };

	int cycle = 2 * (c - 1);
	speed %= cycle;

	int x;
	if (dir == RIGHT) x = pos - 1;
	else x = cycle - (pos - 1);

	int nx = (x + speed) % cycle;

	if (nx < c) return { nx + 1, RIGHT };
	else return { cycle - nx + 1, LEFT };
}

void SharkMove() {
	InitGrid();

	for (int sIdx = 1; sIdx <= m; sIdx++) {
		if (sharks[sIdx].removed) continue;

		int nr = sharks[sIdx].r;
		int nc = sharks[sIdx].c;
		int nd = sharks[sIdx].d;

		if (nd == UP || nd == DOWN) {
			pair<int, int> result = MoveVertical(sharks[sIdx].r, nd, sharks[sIdx].s);
			nr = result.first;
			nd = result.second;
		}
		else {
			pair<int, int> result = MoveHorizontal(sharks[sIdx].c, nd, sharks[sIdx].s);
			nc = result.first;
			nd = result.second;
		}

		sharks[sIdx].r = nr;
		sharks[sIdx].c = nc;
		sharks[sIdx].d = nd;

		if (grid[nr][nc] != EMPTY) {
			int other = grid[nr][nc];
			if (sharks[other].z > sharks[sIdx].z) {
				sharks[sIdx].removed = true;
			}
			else {
				sharks[other].removed = true;
				grid[nr][nc] = sIdx;
			}
		}
		else {
			grid[nr][nc] = sIdx;
		}
	}
}

int main() {
	Init();

	for (int row = 1; row <= c; row++) {
		Fishing(row);

		SharkMove();
	}

	cout << score;

	return 0;
}