[JAVA] BOJ20057 마법사 상어와 토네이도

알고리즘 분류

• 구현
• 시뮬레이션

 

문제 풀이 방법

• 우선 토네이도가 이동하는 경로를 while문을 통해 작성한다.
• 토네이도가 왼쪽으로 이동할 때를 기준으로 해서 모래가 확산될 수 있는 방향 벡터(scatterR, scatterC)를 정의한다.
• 그리고 토네이도가 회전할 때마다 토네이도의 방향벡터의 변화를 확인하면서 모래가 확산될 수 있는 방향벡터도 같이 계산해준다.
• 이번에도 벡터를 활용해서 문제풀이를 하였다. 설명이 부족할 수도 있지만, 내가 문제풀이를 할 때 생각했던 것들을 정리해보았다.
  (왜 이런지 이상하거나, 모르겠으면 질문 고고)

코드

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

/*
 * 마법사 상어와 토네이도
 */

public class Main {
    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N, map[][];
    static long result;
    static int dr[] = {0, 1, 0, -1};
    static int dc[] = {-1, 0, 1, 0};
    static int scatterR[] = {0, -2, 2, 1, 1, 1, -1, -1, -1, 0};
    static int scatterC[] = {-2, 0, 0, -1, 0, 1, -1, 0, 1, -1};
    static double ratio[] = {5, 2, 2, 10, 7, 1, 10, 7, 1};

    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

        for (int r = 0; r < map.length; r++) {
            st = new StringTokenizer(br.readLine());

            for (int c = 0; c < map[r].length; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        Point point = new Point(N / 2, N / 2);

        int l = 0;
        int d = 0;

        L: while(true) {

            if(d == 0 || d == 2) l++;

            int count = 0;

            while(count < l) {
                if(point.r == 0 && point.c == 0) break L;
                int nr = point.r + dr[d];
                int nc = point.c + dc[d];

                func(point.r, point.c, d);

                point.r = nr;
                point.c = nc;

                count++;
            }

            d =  (d + 1) % 4;
        }

        System.out.println(result);
    }

    private static void func(int r, int c, int d) {
        int sum = 0;

        int dirR[] = new int[10];
        int dirC[] = new int[10];

        if(d == 0) {
            dirR = scatterR;
            dirC = scatterC;
        }
        if(d == 1) {
            for(int i = 0; i < 10; i++) {
                dirR[i] = -scatterC[i];
            }
            dirC = scatterR;
        }
        if(d == 2) {
            dirR = scatterR;
            for(int i = 0; i < 10; i++) {
                dirC[i] = -scatterC[i];
            }
        }
        if(d == 3) {
            dirR = scatterC;
            dirC = scatterR;
        }

        r += dr[d];
        c += dc[d];

        for(int i = 0; i < 9; i++) {
            int nr = r + dirR[i];
            int nc = c + dirC[i];

            int tmp = (int) (map[r][c] * ratio[i] / 100);
            sum += tmp;

            if(!check(nr, nc)) { 
                result += tmp;
                continue;
            }

            map[nr][nc] += tmp;
        }

        int nr = r + dr[d];
        int nc = c + dc[d];

        if(!check(nr, nc)) {
            result += (map[r][c] - sum);
        } else {
            map[nr][nc] = map[nr][nc] + map[r][c] - sum;
        }

        map[r][c] = 0;
    }

    private static boolean check(int nr, int nc) {
        return nr >= 0 && nr < N && nc >= 0 && nc < N;
    }
}

 

느낀점

• 시뮬레이션 문제는 한 문제 안에서도 작은 것부터 시작하면서 결국 문제를 해결하는 과정이 재미있는 것 같다. 하지만 이번 문제에서는 수식을 정리하고 디버깅을 하는데 시간을 너무 많이 사용했다. 앞으로 문제풀이를 할 때 집중해서 짧은 시간에 정확하게 풀어보도록 하자!