[백준] 마법사 상어와 토네이도

문제 설명

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

제한사항

• 3 ≤ N ≤ 499
• N은 홀수
• 0 ≤ A[r][c] ≤ 1,000
• 가운데 칸에 있는 모래의 양은 0

---

풀이

50분
작년 하반기 공채 시험장에서 풀어본 문제이다. 사실 풀이법이라고 할 것도 없이 구현하는 것이 전부인 문제지만, 막상 시험장에서 마주치면 어렵게 느껴진다..ㅜ

코드

// 05:38 ~ 06:22
// #pragma warning (disable:4996)
#include<iostream>

using namespace std;

int n;
int board[500][500] = { 0, };
int visit[500][500] = { 0, };

// 위에서 부터 시계방향 
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

bool isvalid(int x, int y){
	if (x >= 0 && x < n && y >= 0 && y < n) return true;
	return false;
}

int main()
{
	// freopen("input.txt", "r", stdin);
	int x, y, dir = 3;
	int init = 0, remain = 0;
	cin >> n;
	x = n / 2;
	y = n / 2;
	visit[x][y] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> board[i][j];
			init += board[i][j];
		}
	}

	while (true) {
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		int sand = board[nx][ny];
		board[nx][ny] = 0;
		visit[nx][ny] = 1;

		//앞
		if (isvalid(nx + dx[dir], ny + dy[dir])) {
			int rest = (int)(sand * 0.05) + 2 * (int)(sand * 0.07) + 2 * (int)(sand * 0.01) + 2 * (int)(sand * 0.02) + 2 * (int)(sand * 0.1);
			board[nx + dx[dir]][ny + dy[dir]] += (sand - rest);
		}
		if (isvalid(nx + 2 * dx[dir], ny + 2 * dy[dir])) {
			board[nx + 2 * dx[dir]][ny + 2 * dy[dir]] += (int)(sand * 0.05);
		}
		
		//우
		if (isvalid(nx + dx[(dir + 1) % 4], ny + dy[(dir + 1) % 4])) {
			board[nx + dx[(dir + 1) % 4]][ny + dy[(dir + 1) % 4]] += (int)(sand * 0.07);
		}
		if (isvalid(nx + 2*dx[(dir + 1) % 4], ny + 2*dy[(dir + 1) % 4])) {
			board[nx + 2*dx[(dir + 1) % 4]][ny + 2*dy[(dir + 1) % 4]] += (int)(sand * 0.02);
		}

		//좌
		if (isvalid(nx + dx[(dir +4 - 1) % 4], ny + dy[(dir + 4 - 1) % 4])) {
			board[nx + dx[(dir + 4 - 1) % 4]][ny + dy[(dir + 4 - 1) % 4]] += (int)(sand * 0.07);
		}
		if (isvalid(nx + 2*dx[(dir + 4 - 1) % 4], ny + 2*dy[(dir + 4 - 1) % 4])) {
			board[nx + 2*dx[(dir + 4 - 1) % 4]][ny + 2*dy[(dir + 4 - 1) % 4]] += (int)(sand * 0.02);
		}

		//정방향 대각선
		if (isvalid(nx + dx[dir] + dx[(dir + 1) % 4], ny + dy[dir] + dy[(dir + 1) % 4])) {
			board[nx + dx[dir] + dx[(dir + 1) % 4]][ny + dy[dir] + dy[(dir + 1) % 4]] += (int)(sand * 0.1);
		}
		if (isvalid(nx + dx[dir] + dx[(dir + 4 - 1) % 4], ny + dy[dir] + dy[(dir + 4 - 1) % 4])) {
			board[nx + dx[dir] + dx[(dir + 4 - 1) % 4]][ny + dy[dir] + dy[(dir + 4 - 1) % 4]] += (int)(sand * 0.1);
		}

		//역방향 대각선
		if (isvalid(nx + dx[(dir + 2) % 4] + dx[(dir + 1) % 4], ny + dy[(dir + 2) % 4] + dy[(dir + 1) % 4])) {
			board[nx + dx[(dir + 2) % 4] + dx[(dir + 1) % 4]][ny + dy[(dir + 2) % 4] + dy[(dir + 1) % 4]] += (int)(sand * 0.01);
		}
		if (isvalid(nx + dx[(dir + 2) % 4] + dx[(dir + 4 - 1) % 4], ny + dy[(dir + 2) % 4] + dy[(dir + 4 - 1) % 4])) {
			board[nx + dx[(dir + 2) % 4] + dx[(dir + 4 - 1) % 4]][ny + dy[(dir + 2) % 4] + dy[(dir + 4 - 1) % 4]] += (int)(sand * 0.01);
		}

		if (visit[nx + dx[(dir + 4 - 1) % 4]][ny + dy[(dir + 4 - 1) % 4]] == 0) dir = (dir + 4 - 1) % 4;

		if (nx == 0 && ny == 0) break; 
		x = nx;
		y = ny;
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			remain += board[i][j];
		}
	}

	cout << init - remain;

	return 0;
}