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

문제

www.acmicpc.net/problem/20057

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

 

풀이

 

반복의 기본단위를 생각해보면 아래와 같다

현재위치에서 다음위치로 이동 → 다음위치에 있는 모래 뿌리기 → 이동한 위치를 현재위치로 업데이트

 

그럼이제 여기서 위의 반복을 언제까지 반복하는지를 생각해보면 "현재위치에서 다음위치로 이동" 했을 때 이동한 위치가 맵영역을 벗어나면 반복을 멈추고 나간모래의 총량을 return 하면 된다.  여기까지의 기본구조는 아래와 같다

 

static int calculateOutSand(int x, int y){
        int outSand = 0;
        
        int currentX = x;
        int currentY = y;

        while (true) {
            //현재위치에서 이동
            int nextX = 0;
            int nextY = 0;
            
            if(nextX<0 || nextY<0 || nextX>=N ||nextY>=N){
                return outSand;
            }
            
            //이동한 위치의 모래 뿌리기
            
            //이동한 위치를 현재위치로 업데이트
            currentX = nextX;
            currentY = nextY;
            
        }
 }

 

 그러면 이제 어떻게 이동하는 지를 구현해야한다. 아래 그림에서 보면 이동하는 방향은 ← ↓→↑ 순서대로 이동한다. 이때 각 이동방향의 이동 횟수를 보면 1 1 2 2 → 3 3 4 4 →  ... 으로 진행된다. 

이동방향의 한 사이클이 끝나면 이동횟수는 각각 +2로 업데이트 된다

 

여기까지 구현을 하면 아래와 같다 

static int[] dx = {0,1,0,-1};   //토네이토의 x 이동 방향
static int[] dy = {-1,0,1,0};   //토네이토의 y 이동 방향
static int[] dc = {1,1,2,2};   // 토네이도의 각 방향으로 이동하는 횟수

static int calculateOutSand(int x, int y){
        int outSand = 0;

        int currentX = x;
        int currentY = y;

        while (true) {
            for(int d = 0; d<4; d++){
                for(int moveCount = 0; moveCount<dc[d]; moveCount++){
                    //현재위치에서 이동
                    int nextX = 0;
                    int nextY = 0;

                    if(nextX<0 || nextY<0 || nextX>=N ||nextY>=N){
                        return outSand;
                    }

                    //이동한 위치의 모래 뿌리기
                    


                    //이동한 위치를 현재위치로 업데이트
                    currentX = nextX;
                    currentY = nextY;
                }
            }

            //횟수 업데이트
            for(int index = 0; index<4; index++){
                dc[index] +=2;
            }
        }
    }

 

이제 모래에 대한 부분을 구현해야한다. 이동한 위치에서 모래가 뿌려지는 규칙은 이동할때의 방향에 따라 달라지는데, 각 방향에 따라 뿌려지는 위치는 아래와 같다

 

최종적으로 정리해보면 아래와 같다.

모래 확산방향을 이동방향에 따라 위치를 구현 하면 아래와 같다 

static int[][] dsx = {{-1,1,-2,-1,1,2,-1,1,0}, {-1,-1,0,0,0,0,1,1,2},    //모래가 퍼지는 x방향
                       {1,-1,2,1,-1,-2,1,-1,0}, {1,1,0,0,0,0,-1,-1,-2}};       
static int[][] dsy = {{1,1,0,0,0,0,-1,-1,-2},{-1,1,-2,-1,1,2,-1,1,0},    //모래가 퍼지는 y방향
                          {-1,-1,0,0,0,0,1,1,2},{1,-1,2,1,-1,-2,1,-1,0}};

 

이제 나머지를 구현하면 된다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] map;
    static int[] dx = {0,1,0,-1};   //토네이토의 x 이동 방향
    static int[] dy = {-1,0,1,0};   //토네이토의 y 이동 방향
    static int[] dc = {1,1,2,2};   // 토네이도의 각 방향으로 이동하는 횟수
    static int[][] dsx = {{-1,1,-2,-1,1,2,-1,1,0}, {-1,-1,0,0,0,0,1,1,2},    //모래가 퍼지는 x방향
                          {1,-1,2,1,-1,-2,1,-1,0}, {1,1,0,0,0,0,-1,-1,-2}};
    static int[][] dsy = {{1,1,0,0,0,0,-1,-1,-2},{-1,1,-2,-1,1,2,-1,1,0},    //모래가 퍼지는 y방향
                          {-1,-1,0,0,0,0,1,1,2},{1,-1,2,1,-1,-2,1,-1,0}};
    static int[] sandRatio ={1,1,2,7,7,2,10,10,5};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine().trim());
        map = new int[N][N];

        for(int r=0; r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<N; c++){
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        int result = calculateOutSand(N/2, N/2);
        bw.write(String.valueOf(result));
        bw.flush();




    }
    //현재위치에서 이동 -> 이동한 위치의 모래 뿌리기 -> 이동한위치를 현재위치로 업데이트
    static int calculateOutSand(int x, int y){
        int totalOutSand = 0;

        int currentX = x;
        int currentY = y;

        while (true) {
            for(int d = 0; d<4; d++){
                for(int moveCount = 0; moveCount<dc[d]; moveCount++){
                    //현재위치에서 이동
                    int nextX = currentX+dx[d];
                    int nextY = currentY+dy[d];

                    if(nextX<0 || nextY<0 || nextX>=N ||nextY>=N){
                        return totalOutSand;
                    }

                    //이동한 위치의 모래 뿌리기
                    int sand = map[nextX][nextY];
                    map[nextX][nextY] = 0;
                    int spreadTotal = 0;


                    for(int spread = 0; spread<9; spread++){
                        int sandX = nextX + dsx[d][spread];
                        int sandY = nextY + dsy[d][spread];
                        int spreadAmount = (sand*sandRatio[spread])/100;

                        if(sandX<0 || sandX>=N || sandY<0 || sandY>=N){
                            totalOutSand += spreadAmount;
                        }
                        else{
                            map[sandX][sandY]+=spreadAmount;
                        }
                        spreadTotal+= spreadAmount;
                    }

                    //알파
                    int alphaX = nextX+dx[d];
                    int alphaY = nextY+dy[d];
                    int alphaAmount = sand -spreadTotal;
                    if(alphaX<0 || alphaX>=N || alphaY<0|| alphaY>=N){
                        totalOutSand +=alphaAmount;
                    }
                    else{
                        map[alphaX][alphaY] +=alphaAmount;
                    }


                    //이동한 위치를 현재위치로 업데이트
                    currentX = nextX;
                    currentY = nextY;
                }
            }

            //횟수 업데이트
            for(int index = 0; index<4; index++){
                dc[index] +=2;
            }
        }
    }

}