[백준/c++] 20057 마법사 상어와 토네이도

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

1) 토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 2) 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

3) 토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다.  4) 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 5) 계산에서 소수점 아래는 버린다.   6) α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다.  7) 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 8) 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 9) (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

제한

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

 

구현해야할 조건

이해하기 정말 까다로운 문제, 나만 까다로웠을지도? 확실한건 이동하는 칸을 상하좌우마다 나눠서 전부 정해주면 되는 문젱제이다. 소수점 아래는 버리기 때문에 주의해주며 모래가 이미 있는 칸으로 모래가 이동하면 모래는 더해진다. 

토네이도가 돌아가는 규칙은 1,1,2,2,3,3,4,4,....n-1,n-1,n이 된다. n개의 칸을 체크한다면 마지막 토네이도라고 보면 된다.

 

code

 

#include<iostream>

#define MAX 510
using namespace std;

const int dy[4] = {0,0,1,-1};
const int dx[4] = {1,-1,0,0};

int ydy[4][10] = { { -1, 1, -1, 1, -1, 1, -2, 2, 0, 0 },{ -1, 1, -1, 1, -1, 1, -2, 2, 0, 0 },
                  { 0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, { 0, 0, -1, -1, -2, -2, -1, -1, -3, -2} };
int xdx[4][10] = { { 0, 0, 1, 1, 2, 2, 1, 1, 3, 2}, { 0, 0, -1, -1, -2, -2, -1, -1, -3, -2},
                  { -1, 1, -1, 1, -1, 1, -2, 2, 0, 0}, {-1, 1, -1, 1, -1, 1, -2, 2, 0, 0} };
int Percent[9] = { 1, 1, 7, 7, 10, 10, 2, 2, 5 }; // right, left, down, up 
int n,res;
int board[MAX][MAX];

int rotate_dir(int dir)
{
	if(dir == 0) return 3; // right -> up 
	if(dir == 1) return 2; // left -> down
	if(dir == 2) return 0; // down -> right
	if(dir == 3) return 1; // up -> left
}

void sand(int y, int x, int dir)
{
	int xx = x + dx[dir];
	int yy = y + dy[dir]; // 한칸 앞에서 
	
	if(board[yy][xx] == 0) // 0이면 옮기는 것 없음 이 점을 유의해야 한다! 
		return;
		
	int s = board[yy][xx];
	int temp = s;
	
	for(int i = 0; i < 9; i++)
	{
		int nx = x + xdx[dir][i];
		int ny = y + ydy[dir][i];
		int per = Percent[i];
		int plus = (temp * per) / 100;
		
		if(nx < 1 || ny < 1 || nx > n || ny > n)
			res += plus; // 범위를 벗어난 것 res 
		else
			board[ny][nx] += plus; // board에 추가 
		
		s -= plus; // 비율 나눈 모래 뺴주기 
	}
	
	int nx = x + xdx[dir][9];
	int ny = y + ydy[dir][9]; // 마지막 alpha 
	
	if(nx < 1 || ny < 1 || nx > n || ny > n)
		res += s;
	else
		board[ny][nx] += s;
	
	board[y][x] = 0;
}

int main()
{
	cin >> n;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			cin >> board[i][j];
	
	int x = (n+1)/2;
	int y = (n+1)/2;
	
	int dir = 1;
	int move_cnt = 1;
	
	while(1)
	{
		for(int i = 0; i < 2; i++)
		{
			for(int j = 0; j < move_cnt; j++) // 1,1,2,2,3,3,4,4,....n-1,n-1,n
			{
				sand(y,x,dir);
				x += dx[dir];
				y += dy[dir];
			}
			
			dir = rotate_dir(dir); // 회전이 바뀌는 것 2번마다 
		}
		
		move_cnt++; // 이동하는 칸의 갯수 
		
		if(move_cnt == n) // 마지막엔 한줄만 퍼트리기 
		{
			for(int j = 0; j < move_cnt; j++)
			{
				sand(y,x,dir);
				x += dx[dir];
				y += dy[dir];
			}
			break;
		}

	}
	
	cout << res;
	return 0;
	
}

 

code [새로 풀이한 코드 내용은 비슷합니다]

#include<iostream>

#define MAX 510
using namespace std;

const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};

/*
이동방향에  맞춰서 문제를 풀어주면 되는 문제입니다. 
xdx, xdy를 정확하게 설계하는것이 우선입니다. 
또한 dx와 dy에 맞춰 방향을 설정해야합니다! 
*/

int xdx[4][10] = {{1,1,0,0,0,0,-1,-1,-2},{-1,1,-2,2,-1,1,-1,1,0},{-1,-1,0,0,0,0,1,1,2},{-1,1,-2,2,-1,1,-1,1,0}};
int ydy[4][10] = {{-1,1,-2,2,-1,1,-1,1,0},{1,1,0,0,0,0,-1,-1,-2},{-1,1,-2,2,-1,1,-1,1,0},{-1,-1,0,0,0,0,1,1,2}};
int Percent[9] = {1,1,2,2,7,7,10,10,5}; 

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

int rotate_dir(int dir)
{
	if(dir == 0) return 3; // down
	if(dir == 1) return 0; // left
	if(dir == 2) return 1; // up
	if(dir == 3) return 2; // right
} 

void sand(int y, int x, int dir)
{
	int xx = x + dx[dir];
	int yy = y + dy[dir]; // 토네이도가 위치한 곳의 sand 위치
	
	if(board[yy][xx] == 0)
		return; // sand의 크기가 0이라면? 굳이 돌릴 필요가 없다.
		
	int s = board[yy][xx]; // sand의 양을 임시 저장
	int temp = s;
	
	for(int i = 0; i < 9; i++) // 9개의 방향으로 돌아가기 때문에 
	{
		int nx = xx + xdx[dir][i];
		int ny = yy + ydy[dir][i];
		int Per = Percent[i];
		
		int sand_plus = (temp * Per) / 100; // 몇퍼센트가 모래의 양에서 퍼지나?
		
		if(nx < 1 || ny < 1 || nx > n || ny > n)
			res += sand_plus; // 나가는 모래를 측정합니다.
		else
			board[ny][nx] += sand_plus;  
			
		s -= sand_plus; // 모래의 양을 제거해주기 
	} 
	
	int nx = x + (dx[dir] * 2);
	int ny = y + (dy[dir] * 2); // 그리고 마지막 남은 모래는 이전
	
	if(nx < 1 || ny < 1 || nx > n || ny > n) // 역시 범위 밖으로 날라갈 수 있다.
		res += s; // 현재 남은 모래 여기가 중요!!
	else
		board[ny][nx] += s;
		
	board[yy][xx] = 0; // 토네이도가 휩쓸은 자리에는 모래가 없다. 
}

int main()
{
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> board[i][j];
		}
	}
	
	int x = (n+1)/2;
	int y = (n+1)/2;
	
	int dir = 0;
	int move_cnt = 1;
	
	while(1)
	{
		/*
		토네이도가 돌아가는 규칙은 두번씩 마지막에는 세번을 돌아갑니다. 
		move_cnt가 증가하면서 토네이도 부는 방향에 움직이는 횟수가 정해집니다. 
		*/
		
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < move_cnt; j++){
				sand(y,x,dir); // 모래를 퍼트리는 일 
				x += dx[dir];
				y += dy[dir]; // 이동을해주고
			}
			dir = rotate_dir(dir);
		}
		
		move_cnt++;
		
		if(move_cnt == n){
			
			for(int j = 0; j < move_cnt; j++){
				
				sand(y,x,dir);
				x += dx[dir];
				y += dy[dir]; // 이동하는 횟수 
			}
			break;
		}
	}
	
	cout << res;
	
	return 0;
}