마법사상어와토네이도-20057번(Java)

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

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

문제

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

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

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

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

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

입력

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

출력

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

제한

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

 

package Samsung;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//문제를 이해하는데 너무 오래걸림
public class 마법사상어와토네이도 {

	static int n;
	static int arr[][];
	static StringTokenizer st;
	
	//방향에 따라 흩뿌려지는 위치가 달라지기 때문에 방향에 따른 흩뿌려지는 위치를 다르게 정해준다.
	//왼,아래,오,위
	static int dx[][] = {{-1,-2,1,2,-1,-1,0,1,1},{0,0,0,0,-1,1,2,1,-1},{-1,-2,1,2,-1,1,0,-1,1},{0,0,0,0,1,-1,-2,-1,1}};
	static int dy[][] = {{0,0,0,0,1,-1,-2,-1,1},{-1,-2,1,2,-1,-1,0,1,1},{0,0,0,0,-1,1,2,1,-1},{-1,-2,1,2,-1,-1,0,1,1}};
	static double p[] = {0.07, 0.02, 0.07, 0.02, 0.01,0.1,0.05,0.1,0.01};
	static int total =0;
	
	static int tx[] = {0,1,0,-1};
	static int ty[] = {-1,0,1,0}; //왼,아래,오,위
	
	public static void print() {
		
		for(int i=0; i<n;i++) {
			for(int j=0; j<n; j++) {
				
				System.out.print(arr[i][j]+" ");
			}
			
			System.out.println();
		}
		
		System.out.println();
	}
	
	public static boolean cango(int x, int y) {
		
		
		return x>=0 && x<n && y>=0 && y<n;
		
	}
	
	public static void seperate(int x, int y, int tmp, int d) {
		
	
		
		for(int i=0; i<9; i++) {
			
			int nx = x+dx[d][i];
			int ny = y+dy[d][i];
			int mo =(int) (arr[x][y]*p[i]); //(x,y)에서 비율을 곱해준다
			if(!cango(nx,ny)) { //흩어진 모래가 좌표를 넘어간 경우
				
				total += mo; //넘어간 모래 크기만큼 더해준다
				tmp-=mo; //흩어진 모래를 빼준다.
				continue;
			}
			
			arr[nx][ny]+=mo; //흩어져서 nx,ny 에 도착한 모래를 더해준다
			tmp-=mo;//흩어진 모래를 빼준다.
			
		}
		
		arr[x][y]=0; //기존 x,y 는 0이되고 그 다음 칸에 넘겨줘야함
		x=x+tx[d];
		y=y+ty[d];// x,y 에서 d 방향으로 한칸 더간곳에 넘겨준다
		if(cango(x,y))arr[x][y]+=tmp; //넘겨줄 곳이 좌표 안이라면 더해준다
		else total+=tmp; //좌표 안이 아니라면 total에 더해준다

	}
	
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n][n];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				
				arr[i][j]= Integer.parseInt(st.nextToken());
			}
		}
		
		int x = n/2;
		int y = n/2;
		
		int c =1;

		int i=0; //방향
		boolean tg = false; //사라지는 지점에 도착했는지 여부를 알려주는 토글 버튼
		while(true) {
			
		
			
			for(int t=0; t<c; t++) { //크기 c 만큼 움직인다.
			int nx = x+tx[i]; //현재 방향으로 한칸 움직인 좌표.
			int ny = y+ty[i];   //현재 방향으로 한칸 움직인 좌표.
		
			if(x==0 && y==0) {total+=arr[x][y];tg=true;break;} // 0,0 좌표에 오면 토네이도가 없어진다.
			
			seperate(nx, ny,arr[nx][ny],i); //모래 흐트리기

			x= nx;
			y= ny;
//			print();
			}
			if(tg)break;
			int ni = (i+1)%4; //방향 바꿔주기
			if(i==1 && ni==2) {c++;} //아래->오 갈때 움직일 거리를 1늘려준다 
			else if(i==3 && ni==0) {c++;} //위->왼 갈때 움직일 거리를 1늘려준다
			i=ni;
			
		}
		
		
		System.out.println(total);
		
		
		
	}
	
	
	
}

- 방향에 따라 비율이 적용되는 위치가 달라지는것 주의!