알고리즘 문제풀이:: 백준 삼성SW 20057 마법사 상어와 토네이도

참고자료

https://kimjingo.tistory.com/37

백준 풀이 - 2차원 배열의 나선형 알고리즘

문제리뷰

20057 마법사 상어와 토네이도 (골드3)

 

피드백

나선형 알고리즘만 잘 구현하면 되는 문제

단, 토네이도가 회전 시 모래에 적용되는 비율도 같이 회전해야 해서

비율 회전 관련된 배열이 필요하다는 것을 주의해야 함

그리고 비율에 float 자료형 적용하는거 잊지 말자..

---

C++

20057 마법사 상어와 토네이도

#include <iostream>
#define MAX 500
#define X first
#define Y second
using namespace std;

int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
float sand[] = { 0.05, 0.1, 0.1, 0.02, 0.07, 0.07, 0.02, 0.01, 0.01 };
int sx[4][9] = {
	{ 0, 1, -1, 2, 1, -1, -2, 1, -1 },
	{ 2, 1, 1, 0, 0, 0, 0, -1, -1 },
	{ 0, -1, 1, -2, -1, 1, 2, -1, 1 },
	{ -2, -1, -1, 0, 0, 0, 0, 1, 1 }
};
int sy[4][9] = {
	{ -2, -1, -1, 0, 0, 0, 0, 1, 1 },
	{ 0, -1, 1, -2, -1, 1, 2, -1, 1 },
	{ 2, 1, 1, 0, 0, 0, 0, -1, -1 },
	{ 0, 1, -1, 2, 1, -1, -2, 1, -1}
};

int n, answer;
int board[MAX][MAX];

void input() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> board[i][j];
		}
	}
}

void solution() {
	int dir = 0;
	int length = 1;
	int moveCnt = 0;
	int x = n / 2, y = n / 2;
	while (true) {
		moveCnt++;
		for (int i = 0; i < length; i++) {
			x += dx[dir];
			y += dy[dir];

			if (x == 0 && y == -1) return;

			int base = board[x][y];
			for (int j = 0; j < 9; j++) {
				int nx = x + sx[dir][j];
				int ny = y + sy[dir][j];
				int s = board[x][y] * sand[j];
				base -= s;

				if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
					answer += s;
				}
				else {
					board[nx][ny] += s;
				}
			}

			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
				answer += base;
			}
			else {
				board[nx][ny] += base;
			}
			board[x][y] = 0;
		}

		if (moveCnt == 2) {
			length++;
			moveCnt = 0;
		}
		dir = (dir + 1) % 4;
	}
}

void solve() {
	input();
	solution();
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	solve();
	cout << answer << '\n';
}