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

문제

---

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)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

 

 

 

 

 

풀이

---

구현, 시뮬레이션 특성상 문제에서 제시하는 대로 구현을 하면된다.

 

우선 방향에 따라서 범위를 직접 계산해서 저장했다.

static int[][] sandR = { { -1, 1, -2, 2, -1, 1, -1, 1, 0, 0}, 
							{0, 0, 1, 1, 1, 1, 2, 2, 3, 2},
							{-1, 1, -2, 2, -1, 1, -1, 1, 0, 0},
							{0, 0, -1, -1, -1, -1, -2, -2, -3, -2}};

static int[][] sandC = { { 0, 0, -1, -1, -1, -1, -2, -2, -3, -2}, 
							{-1, 1, -2, 2, -1, 1, -1, 1, 0, 0},
							{0, 0, 1, 1, 1, 1, 2, 2, 3, 2},
							{-1, 1, -2, 2, -1, 1, -1, 1, 0, 0}};

0번 부터 차례대로 좌, 하, 우, 상 방향으로 범위를 비율 범위를 지정하는 것이다.

 

static double[] percentage = { 0.01, 0.01, 0.02, 0.02, 0.07, 0.07, 0.1, 0.1, 0.05};

그 때의 위치마다 비율을 미리 정해둔다.

 

마지막은 알파 범위다. 알파는 비율로 모래를 뿌리고 남은 모래가 한꺼번에 들어간다.

여기서 체크해야하는게 소수점 아래는 버려지기때문에 1보다 작은 모래는 날아가지 않고 그자리에 있게된다.

그래서, 날아간 모래를 제외한 모든 모레가 알파로 가게된다.

public static void moveSand(int r, int c, int nr, int nc, int dir) {
	
	int sum = 0;
	for(int i = 0 ; i < 9 ; i++) {
		int sr = r + sandR[dir][i];
		int sc = c + sandC[dir][i];
		
		int amountSand = (int)Math.floor((double)A[nr][nc] * percentage[i]);
		if(!isIn(sr, sc)) {
			answer += amountSand;
		}
		else {
			A[sr][sc] += amountSand; 
		}	
		
		sum += amountSand;
	}
	
	r += sandR[dir][9];
	c += sandC[dir][9];
	
	if(isIn(r,c)) {
		A[r][c] += A[nr][nc] - sum;
	}
	else {
		answer += A[nr][nc] - sum;
	}
	
	
	return;
}

범위 안에있다면 옮겨주고 범위 밖이라면 answer에 더해준다.

 

 

토네이도의 이동은 두번 상하로 이동 후에 다음 변으로 갈때는 전보다 하나씩 더 이동한다는 것을 이용해서 풀었다.

while(r != 0 || c != 0) {
	
	for(int i = 0 ; i < cnt ; i++){
		
		moveSand(r, c, r + move[dir][0], c + move[dir][1], dir);
		r += move[dir][0];
		c += move[dir][1];	
		
		A[r][c] = 0;
		
		if(r == 0 && c == 0) {
			break;
		}
	}
	
	if(dir % 2 == 1) {
		cnt++;
	}			
	dir = (dir + 1) % 4;
}

cnt 만큼 한방향으로 이동하고, 이동이 끝나면 dir 을 바꿔 방향을 바꿔준다.

이 때, dir 이 상, 하 를 지나가면 cnt 를 하나 늘려준다.

 

그림을 그려보면 이해하기 편할 것이다.

 

 

<전체코드>

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

public class Main {
	
	static int[][] A;
	static int answer = 0;
	static int[][] move = { {0, -1}, {1, 0}, {0, 1}, {-1, 0}};
	static double[] percentage = { 0.01, 0.01, 0.02, 0.02, 0.07, 0.07, 0.1, 0.1, 0.05};
	static int[][] sandR = { { -1, 1, -2, 2, -1, 1, -1, 1, 0, 0}, 
								{0, 0, 1, 1, 1, 1, 2, 2, 3, 2},
								{-1, 1, -2, 2, -1, 1, -1, 1, 0, 0},
								{0, 0, -1, -1, -1, -1, -2, -2, -3, -2}};
	
	static int[][] sandC = { { 0, 0, -1, -1, -1, -1, -2, -2, -3, -2}, 
								{-1, 1, -2, 2, -1, 1, -1, 1, 0, 0},
								{0, 0, 1, 1, 1, 1, 2, 2, 3, 2},
								{-1, 1, -2, 2, -1, 1, -1, 1, 0, 0}};
	static int n;
	
	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		n = parseInt(bufferedReader.readLine());
		
		A = new int[n][n];
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			for(int j = 0 ; j < n ; j++) {
				A[i][j] = parseInt(st.nextToken());
			}			
		}
		
		moveTonado();
		
		System.out.println(answer);
	}
	
	public static boolean isIn(int r, int c) {
		
		if( r < 0 || r >= n || c < 0 || c >= n) {
			return false;
		}
		
		return true;
	}
	
	public static void moveSand(int r, int c, int nr, int nc, int dir) {
		
		int sum = 0;
		for(int i = 0 ; i < 9 ; i++) {
			int sr = r + sandR[dir][i];
			int sc = c + sandC[dir][i];
			
			int amountSand = (int)Math.floor((double)A[nr][nc] * percentage[i]);
			if(!isIn(sr, sc)) {
				answer += amountSand;
			}
			else {
				A[sr][sc] += amountSand; 
			}	
			
			sum += amountSand;
		}
		
		r += sandR[dir][9];
		c += sandC[dir][9];
		
		if(isIn(r,c)) {
			A[r][c] += A[nr][nc] - sum;
		}
		else {
			answer += A[nr][nc] - sum;
		}
		
		
		return;
	}
	
	public static void moveTonado() {
		
		int r = n / 2;
		int c = n / 2;
		int dir = 0;
		int cnt = 1;
		while(r != 0 || c != 0) {
			
			for(int i = 0 ; i < cnt ; i++){
				
				moveSand(r, c, r + move[dir][0], c + move[dir][1], dir);
				r += move[dir][0];
				c += move[dir][1];	
				
				A[r][c] = 0;
				
				if(r == 0 && c == 0) {
					break;
				}
			}
			
			if(dir % 2 == 1) {
				cnt++;
			}			
			dir = (dir + 1) % 4;
		}
	}
}