μ•Œκ³ λ¦¬μ¦˜

[ λ°±μ€€ / BOJ 20057 ] λ§ˆλ²•μ‚¬ 상어와 토넀이도 ( μžλ°” / JAVA )

KIMHYEYUN 2022. 2. 7. 17:07
λ°˜μ‘ν˜•

 

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

 

20057번: λ§ˆλ²•μ‚¬ 상어와 토넀이도

λ§ˆλ²•μ‚¬ 상어가 토넀이도λ₯Ό λ°°μ› κ³ , μ˜€λŠ˜μ€ 토넀이도λ₯Ό 크기가 N×N인 격자둜 λ‚˜λˆ„μ–΄μ§„ λͺ¨λž˜λ°­μ—μ„œ μ—°μŠ΅ν•˜λ €κ³  ν•œλ‹€. μœ„μΉ˜ (r, c)λŠ” 격자의 rν–‰ c열을 μ˜λ―Έν•˜κ³ , A[r][c]λŠ” (r, c)에 μžˆλŠ” λͺ¨λž˜μ˜ 양을

www.acmicpc.net

문제 μ„€λͺ…

토넀이도 μ‹œμ „ μ‹œ

λ°©μ‹μœΌλ‘œ 이동이 μ‹œμž‘λ¨

xκ°€ y둜 이동할 λ•Œ, y의 λͺ¨λž˜κ°€ λΉ„μœ¨κ³Ό $\alpha$κ°€ μ ν˜€μžˆλŠ” 칸으둜 이동
$\alpha$ = 총 μ–‘ - λΉ„μœ¨ μΉΈ 이동양
λͺ¨λž˜λŠ” λ²”μœ„ λ°–μœΌλ‘œ 이동 κ°€λŠ₯! πŸ‘‰ 사라짐

ν† λ„€μ΄λ„λŠ” (0,0)κΉŒμ§€ μ΄λ™ν•œ λ’€ μ†Œλ©Έλ¨
μ†Œλ©Έλœ ν›„, 격자 λ°–μœΌλ‘œ λ‚˜κ°„ λͺ¨λž˜μ˜ μ–‘ 좜λ ₯

문제 풀이

λ°©ν–₯에 따라 λΏŒλ €μ§€λŠ” μœ„μΉ˜

이동방ν–₯
μ΄λ™νšŸμˆ˜ 1,3,5,..., 1,3,5,..., 2,4,6,..., 2,4,6,...,
λͺ¨λž˜ ν™•μ‚° λ°©ν–₯

dx/dyOfSand[4][9] πŸ‘‰ 4λ°©ν–₯μ—μ„œ 각 λΉ„μœ¨μ˜ μœ„μΉ˜
ratioOfSand[9] πŸ‘‰ dx/dyOfSand μˆœμ„œλŒ€λ‘œμ˜ λΉ„μœ¨ {2, 10, 7, 1, 5, 10, 7, 1, 2}

νšŒμ „ν•˜λ©΄μ„œ, λͺ¨λž˜κ°€ νΌμ§€λŠ” μœ„μΉ˜(x,y)κ°€ (x < 0 || y < 0 || N <= x || N <= y)이면
amountOfOutSand에 μΆ”κ°€ν•΄μ€€λ‹€

~

!!!

μ½”λ“œ

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

public class Main_BOJ_20057_λ§ˆλ²•μ‚¬_상어와_토넀이도 {

    static int N, amountOfOutSand = 0;
    static int[][] map;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    static int[] numOfMove = {1, 1, 2, 2};
    static int[][] dxOfSand = {{-2, -1, -1, -1, 0, 1, 1, 1, 2}, {0, 1, 0, -1, 2, 1, 0, - 1, 0}, {2, 1, 1, 1, 0, -1, -1, -1, -2}, {0, -1, 0, 1, -2, -1, 0, 1, 0}};
    static int[][] dyOfSand = {{0, -1, 0, 1, -2, -1, 0, 1, 0}, {-2, -1, -1, -1, 0, 1, 1, 1, 2}, {0, 1, 0, -1, 2, 1, 0, -1, 0}, {2, 1, 1, 1, 0, -1, -1, -1, -2}};
    static int[] ratioOfSand = {2, 10, 7, 1, 5, 10, 7, 1, 2};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        tornado(N / 2, N / 2);

        System.out.println(amountOfOutSand);
    }

    private static void tornado(int x, int y) {

        int curX = x;
        int curY = y;

        while (true) {
            for (int d = 0; d < 4; d++) {
                for (int i = 0; i < numOfMove[d]; i++) {
                    int nx = curX + dx[d];
                    int ny = curY + dy[d];

                    if (nx < 0 || ny < 0 || N <= nx || N <= ny) return;

                    int sand = map[nx][ny];
                    map[nx][ny] = 0;
                    int spreadTotal = 0;

                    for (int s = 0; s < 9; s++) {
                        int sandX = nx + dxOfSand[d][s];
                        int sandY = ny + dyOfSand[d][s];
                        int spreadAmount = (sand * ratioOfSand[s]) / 100;

                        if (sandX < 0 || sandY < 0 || N <= sandX || N <= sandY) amountOfOutSand += spreadAmount;
                        else map[sandX][sandY] += spreadAmount;

                        spreadTotal += spreadAmount;
                    }

                    int alphaX = nx + dx[d];
                    int alphaY = ny + dy[d];
                    int amountOfAlpha = sand - spreadTotal;

                    if (alphaX < 0 || alphaY < 0 || N <= alphaX || N <= alphaY) amountOfOutSand += amountOfAlpha;
                    else map[alphaX][alphaY] += amountOfAlpha;

                    curX = nx;
                    curY = ny;


                    /*for(int[] ma : map){
                        for(int m : ma){
                            System.out.print(m+" ");
                        }
                        System.out.println();
                    }
                    System.out.println();*/
                }
            }

            for (int i = 0; i < 4; i++) {
                numOfMove[i] += 2;
            }
        }
    }
}
728x90
λ°˜μ‘ν˜•