[백준]JAVA - 20057번: 마법사 상어와 토네이도

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

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

풀이

위 문제는 맵 격자의 가운데 칸부터 토네이도가 이동을 시작한다.

한 번에 한 칸씩 이동하며 모래는 아래와 같은 비율로 흩날리게 된다.

static double[] per = {1,1,2,2,7,7,10,10,5,0};
static int[][] sdx = {
    {-1,1,-2,2,-1,1,-1,1,0,0}, // 좌 
    {-1,-1,0,0,0,0,1,1,2,1},   // 하 
    {-1,1,-2,2,-1,1,-1,1,0,0}, // 우
    {1,1,0,0,0,0,-1,-1,-2,-1}, // 상 
};
static int[][] sdy = {
    {1,1,0,0,0,0,-1,-1,-2,-1}, // 좌 
    {-1,1,-2,2,-1,1,-1,1,0,0}, // 하 
    {-1,-1,0,0,0,0,1,1,2,1},   // 우
    {-1,1,-2,2,-1,1,-1,1,0,0}, // 상 
};

4개의 방향으로 이동한다. 토네이도가 움직이는 방향에 따라서 흩날리는 모래의 위치 (x, y)가 달라진다. 미리 모래의 비율과 흩날리는 위치를 미리 넣어두고 시작하면 구현이 편해진다. 여기서 중요한 건 x 위치의 모래가 아닌 y 위치에 있는 모래가 흩날리며, a 에는 흩날리고 남은 모래가 남는다.

 

먼저 토네이도 이동에 대해서 알아보겠다.

토네이도 이동을 자세히 살펴보면 아래와 같은 규칙을 찾을 수 있다.

1칸, 1칸, 2칸, 2칸, ··· 

좌방향부터 시작해서 방향을 2번을 바꿀 때마다 1칸씩 증가한다. 

public static void Move(int x, int y) {
    int[] changeOfDir = {1, 1, 2, 2};
    double ySand;
        
    while (true) {
        for (int d=0; d<4; d++) {
            for (int i=0; i<changeOfDir[d]; i++) {
                x += dx[d];
                y += dy[d];
                    
                ySand = map[x][y]; 
                
                if (ySand > 0) {
                    spread(x, y, d, ySand);
                }
                    
                if (x == 0 && y == 0) {
                    return;
                }
            }
        }
            
        for (int k=0; k<4; k++) {
            changeOfDir[k] += 2;
        }
    }
}

위 규칙으로 모든 칸을 이동하면서 모래의 비율만큼 해당 칸에 뿌려주면 된다.

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    static double[] per = {1,1,2,2,7,7,10,10,5,0};
    static int[][] sdx = {
            {-1,1,-2,2,-1,1,-1,1,0,0}, // 좌 
            {-1,-1,0,0,0,0,1,1,2,1}, // 하 
            {-1,1,-2,2,-1,1,-1,1,0,0}, // 우
            {1,1,0,0,0,0,-1,-1,-2,-1}, // 상 
    };
    static int[][] sdy = {
            {1,1,0,0,0,0,-1,-1,-2,-1}, // 좌 
            {-1,1,-2,2,-1,1,-1,1,0,0}, // 하 
            {-1,-1,0,0,0,0,1,1,2,1}, // 우
            {-1,1,-2,2,-1,1,-1,1,0,0}, // 상 
    };
    
    static int[][] map;
    static int N;
    static int ans = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        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());
            }
        }
        
        Move(N/2, N/2);
        System.out.println(ans);
    }
    
    public static void Move(int x, int y) {
        int[] changeOfDir = {1, 1, 2, 2};
        double ySand;
        
        while (true) {
            for (int d=0; d<4; d++) {
                for (int i=0; i<changeOfDir[d]; i++) {
                    x += dx[d];
                    y += dy[d];
                    
                    ySand = map[x][y]; 
                
                    if (ySand > 0) {
                        spread(x, y, d, ySand);
                    }
                    
                    if (x == 0 && y == 0) {
                        return;
                    }
                }
            }
            
            for (int k=0; k<4; k++) {
                changeOfDir[k] += 2;
            }
        }
    }
    
    public static void spread(int x, int y, int d, double ySand) {
        int nx, ny;
        double spreadSands = 0; // 이동한 모래 양 
        
        // 남은 모래는 a 위치로 이동하기때문에 0 
        map[x][y] = 0;
        
        for(int i=0; i<10; i++) {
            nx = x + sdx[d][i];
            ny = y + sdy[d][i];
            
            int sand = (int) Math.floor(ySand / 100 * per[i]);
            
            if (i == 9) {
               
                double aSand = ySand - spreadSands; // 이동하고 남은 모래 양
                
                if (!RangeCheck(nx,ny)) {
                    ans += aSand;
                } else {
                    map[nx][ny] += aSand;
                }
            } else {
                if (!RangeCheck(nx,ny)) {
                    ans += sand;
                } else {
                    map[nx][ny] += sand; 
                }
                spreadSands += sand;
            }
            
        }
    }
    
    public static boolean RangeCheck(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N ? true : false;
    }
}