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

❓ 문제 - 백준 마법사 상어와 토네이도 20057번 - JAVA 풀이법

 

출처

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

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

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• 좌, 하, 우, 상 각 방향으로 이동했을 때 흩어지는 모래양의 퍼센트를 moving이라는 3차원 배열을 통해 맞춰서 구현해준다. 알파일 때는 -1로 둔다. ans라는 변수로 격자밖으로 넘어간 양의 모래를 저장한다.
• 처음 토네이도의 일정 방향으로 이동 처리를 구현할 때 좌 -> 하 -> 우 -> 상을 반복하면서 이동하며 각각 방향에 맞춰서는 1, 1, 2, 2, 3, 3, ..., n-1, n-1, n 칸씩 일정한 방향을 유지한 채 이동하다가 방향을 바꾼다. 이를 맞춰서 구현해준다. num은 방향 유지 횟수이며, smae_dir_cnt은 한 방향으로 몇 번 이동했는지 저장한다.
• dir이 0, 1 / 2, 3 일 때 방향을 유지하는 횟수는 동일하므로 횟수의 유지 숫자는 same_num_cnt로 관리한다. 현재 횟수의 유지 숫자가 1이면서  방향을 변경해야할 때 num을 1증가해준다. 
• move 함수를 통해 토네이도가 이동 한 위치 (x,y)을 기준으로 (x-2 ~ x+2), (y-2 ~ x+2)까지 moving 배열로 모래 움직임 처리를 한다.
• 만약 -1인 경우는 알파이므로 해당 알파에 대한 x, y정보를 저장한다. cnt로 얼만큼 모래가 흩날렸는지 저장한다. 퍼센트가 있는 곳은 현재 모래양을 기준으로 퍼센트에 해당되는 부분을 더해주고 cnt에 값을 더해준다. 그리고 격자를 넘어가는 부분은 해당 모래 양은 ans에 더해준다. 그리고 모래를 다 옮기고 나서 남아있는 모래 양은 알파인 부분에 더해준다.

 

💻 소스코드

// BOJ - 마법사 상어와 토네이도(20057번)
// 구현

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

public class Main {
	public static int n, ans;
	public static int[][] map;
	public static int[] dx = {0, 1, 0, -1};
	public static int[] dy = {-1, 0, 1, 0};
	public static int[][][] moving = {
			{{0, 0, 2, 0, 0}, {0, 10, 7, 1, 0}, {5, -1, 0, 0, 0}, {0, 10, 7, 1, 0}, {0, 0, 2, 0, 0}},
			{{0, 0, 0, 0, 0}, {0, 1, 0, 1, 0}, {2, 7, 0, 7, 2}, {0, 10, -1, 10, 0}, {0, 0, 5, 0, 0}},
			{{0, 0, 2, 0, 0}, {0, 1, 7, 10 ,0}, {0, 0, 0, -1, 5}, {0, 1, 7, 10, 0}, {0, 0, 2, 0, 0}},
			{{0, 0, 5, 0, 0}, {0, 10, -1, 10, 0}, {2, 7, 0, 7, 2}, {0, 1, 0, 1, 0}, {0, 0, 0, 0, 0}}
	};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int x = n/2;
		int y = n/2;
	
		int dir = 0;
		int num = 1;
		int same_dir_cnt = 0;
		int same_num_cnt = 0;
		ans = 0;
		outer: while(true) {
		
			while(true) {
				int nx = x + dx[dir];
				int ny = y + dy[dir];
				same_dir_cnt++;
		
				if(map[nx][ny] != 0) {
					move(nx, ny, dir);
				}
				x = nx;
				y = ny;
				if(same_dir_cnt == num) {
					if(same_num_cnt == 0) {
						same_dir_cnt = 0;
						same_num_cnt++;
					} else {
						same_dir_cnt = 0;
						same_num_cnt = 0;
						num++;
					}
					break;
				}
				if(x == 0 && y == 0) break outer;
			}
		
			dir = (dir+1) % 4;
			
		}
		
		
		
		System.out.println(ans);
	}
	
	public static void move(int x, int y, int dir) {
		int alph_x = -1;
		int alph_y = -1;
		int origin = map[x][y];
		int cnt = 0;
		
		for(int i=x-2;i<=x+2;i++) {
			for(int j=y-2;j<=y+2;j++) {
				int a = i-(x-2);
				int b = j-(y-2);
				if(moving[dir][a][b] == 0) continue;
				if(moving[dir][a][b] == -1) {
					alph_x = i;
					alph_y = j;
					continue;
				}
				
				double percent = (double) moving[dir][a][b] / 100;
				int sand = (int)(origin * (percent));
				cnt += sand;
				
				if(i < 0 || i >= n || j < 0 || j >= n) {
					ans += sand;
				} else {
					map[i][j] += sand;
				}
			}
		}
		
		if(alph_x < 0 || alph_x >= n || alph_y < 0 || alph_y >= n) {
			ans += (origin-cnt);
		} else {
			map[alph_x][alph_y] += (origin-cnt);
		}
		map[x][y] = 0;
	}

}