[Algorithm][C++] BOJ 20057 마법사 상어와 토네이도

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

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

 

풀이 핵심

1. 구현 / 시뮬레이션 문제

 

2. 미리 모래 날리는 비율, 왼/아래/오른/위 방향에 따른 모래 이동 위치 배열들을 생성해야 한다.

// 토네이도 이동 배열
const int dy[] = { 0,1,0,-1 };
const int dx[] = { -1,0,1,0 };
// 비율 정보를 담고 있는 배열
const int ratio[9] = { 1,2,7,10,5,10,7,2,1 };
// 모래 날리는 이동 배열
const int dr[4][10] = {
	{-1,-2,-1,-1,0,1,1,2,1,0},
	{-1,0,0,1,2,1,0,0,-1,1},
	{-1,-2,-1,-1,0,1,1,2,1,0},
	{1,0,0,-1,-2,-1,0,0,1,-1}
};
const int dc[4][10] = {
	{1,0,0,-1,-2,-1,0,0,1,-1},
	{-1,-2,-1,-1,0,1,1,2,1,0},
	{-1,0,0,1,2,1,0,0,-1,1},
	{1,2,1,1,0,-1,-1,-2,-1,0}
};

 

3. 토네이도가 이동 횟수 (왼쪽으로 2번 아래로 2번 오른쪽으로 3번 위로 3번 왼쪽으로 4번...) 는 다음과 같이 실수를 활용해 구현한다.

...
for (double i = 1.0; i <= N; i += 0.5) {
  for (int j = 0; j < (int)i; j++) {
    y += dy[dir % 4], x += dx[dir % 4];
    sand_out += get_sand_out(y, x, dir);
  }
  dir++;
}
...

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>

int N;
int map[499][499];
const int dy[] = { 0,1,0,-1 };
const int dx[] = { -1,0,1,0 };
const int ratio[9] = { 1,2,7,10,5,10,7,2,1 };
const int dr[4][10] = {
	{-1,-2,-1,-1,0,1,1,2,1,0},
	{-1,0,0,1,2,1,0,0,-1,1},
	{-1,-2,-1,-1,0,1,1,2,1,0},
	{1,0,0,-1,-2,-1,0,0,1,-1}
};
const int dc[4][10] = {
	{1,0,0,-1,-2,-1,0,0,1,-1},
	{-1,-2,-1,-1,0,1,1,2,1,0},
	{-1,0,0,1,2,1,0,0,-1,1},
	{1,2,1,1,0,-1,-1,-2,-1,0}
};

int get_sand_out(int y, int x, int dir) {
	int ret = 0;
	int cur_sand = map[y][x];
	
	for (int i = 0; i < 10; i++) {
		int sand;
		if (i != 9) {
			sand = cur_sand * ratio[i] / 100;
			map[y][x] -= sand;
		}
		else {
			sand = map[y][x];
			map[y][x] = 0;
		}
		int nr = y + dr[dir % 4][i];
		int nc = x + dc[dir % 4][i];
		if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
			ret += sand;
			continue;
		}

		map[nr][nc] += sand;
	}
	
	return ret;
}

int main() {
	int sand_out = 0;
	scanf("%d", &N);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &map[r][c]);
		}
	}
	int y = N / 2, x = N / 2, dir = 0;
	for (double i = 1.0; i <= N; i += 0.5) {
		for (int j = 0; j < (int)i; j++) {
			y += dy[dir % 4], x += dx[dir % 4];
			sand_out += get_sand_out(y, x, dir);
		}
		dir++;
	}
	printf("%d", sand_out);
	return 0;
}