백준 20057번 : 마법사 상어와 토네이도

sol : 104' 10''

• 수행 시간 : 88ms -> 32ms
• 메모리 : 2996KB

Learnings

• 하드코딩말고 뭔가 더 멋있게 할 수 있는데 당장 생각이 안났다.
• cin.tie(0)->sync_with_stdio(0) 이거 꼭 쓰자.

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

#define MAX_N 500
#define LEFT 0
#define DOWN 1
#define RIGHT 2
#define UP 3

int grid[MAX_N][MAX_N];
// 좌, 하, 우, 상
const int ds[4][2] = { { 0, -1 }, {1, 0}, {0, 1}, {-1, 0} };
const double area[4][9][3] = 
{ 
	// LEFT
	{{-2, 0, 0.02},
	{-1, -1, 0.1},
	{-1, 0, 0.07},
	{-1, 1, 0.01},
	{0, -2, 0.05},
	{1, -1, 0.1},
	{1, 0, 0.07},
	{1, 1, 0.01},
	{2, 0, 0.02}},

	// DOWN
	{{0, 2, 0.02},
	{0, 1, 0.07},
	{0, -1, 0.07},
	{0, -2, 0.02},
	{-1, 1, 0.01},
	{-1, -1, 0.01},
	{1, 1, 0.1},
	{1, -1, 0.1},
	{2, 0, 0.05}},

	// RIGHT
	{{-1, -1, 0.01},
	{1, -1, 0.01},
	{2, 0, 0.02},
	{1, 0, 0.07},
	{-1, 0, 0.07},
	{-2, 0, 0.02},
	{1, 1, 0.1},
	{-1, 1, 0.1},
	{0, 2, 0.05}},
	
	// UP
    {{1, -1, 0.01},
	{1, 1, 0.01},
	{0, -2, 0.02},
	{0, -1, 0.07},
	{0, 1, 0.07},
	{0, 2, 0.02},
	{-1, -1, 0.1},
	{-1, 1, 0.1},
	{-2, 0, 0.05}}
};

int n;
int outSand;

void Init() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
		}
	}
}

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

void Split(int i, int j, int dir) {
	int sand = grid[i][j], restSand = grid[i][j];
	grid[i][j] = 0;

	for (int da = 0; da < 9; da++) {
		int ni = i + area[dir][da][0], nj = j + area[dir][da][1];
		int ns = sand * area[dir][da][2];

		restSand -= ns;
		if (InGrid(ni, nj)) grid[ni][nj] += ns;
		else outSand += ns;
	}

	int ri = i + ds[dir][0], rj = j + ds[dir][1];
	if (InGrid(ri, rj)) grid[ri][rj] += restSand;
	else outSand += restSand;
}

void Wind() {
	bool leftDown = false;
	int ci = n / 2 + 1, cj = n / 2 + 1;
	for (int i = 1; i < n; i++) {
		leftDown ^= 1;
		if (leftDown) {
			// left
			for (int di = 1; di <= i; di++) {
				ci += ds[LEFT][0], cj += ds[LEFT][1];
				Split(ci, cj, LEFT);
			}
			// down
			for (int di = 1; di <= i; di++) {
				ci += ds[DOWN][0], cj += ds[DOWN][1];
				Split(ci, cj, DOWN);
			}
		}
		else {
			// right
			for (int di = 1; di <= i; di++) {
				ci += ds[RIGHT][0], cj += ds[RIGHT][1];
				Split(ci, cj, RIGHT);
			}
			// up
			for (int di = 1; di <= i; di++) {
				ci += ds[UP][0], cj += ds[UP][1];
				Split(ci, cj, UP);
			}
		}
	}
	// 1행 처리
	for (int j = n - 1; j > 0; j--) {
		Split(1, j, LEFT);
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	Init();

	Wind();

	cout << outSand;

	return 0;
}