[알고리즘 / 백준] 20057 - 마법사 상어와 토네이도

www.acmicpc.net/problem/20057

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

 문제는 위와 같으며, 이 문제는 각 위치로 이동하면서 이동할 때마다 주변으로 날리는 모래를 계산하여 모래밭 내에 포함되면 해당 위치 모래에 추가하고 벗어나면 최종 결과에 추가하는 방식으로 문제를 해결하였습니다.

 

각 방향마다 그에 맞는 먼지 날리는 비율이 달라지므로 왼쪽, 아래, 오른쪽, 위 방향으로 각각 기준점으로부터 이동할 위치 x, y 와 그때 해당하는 비율을 미리 저장해뒀다가 경우에 맞게 사용하였습니다... 더 좋은 규칙을 찾을 수 있다면 해당 부분의 반복(?)을 조금은 줄일 수 있겠지만 지금 생각으로는 이 방법 밖에 안떠올라서 우선 글을 적어봅니다...

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

# 왼쪽으로 갈 때 위치와 비율
l_rate = [
    [-2, 0, 0.02], [2, 0, 0.02],
    [-1, -1, 0.1], [-1, 0, 0.07], [-1, 1, 0.01], [1, -1, 0.1], [1, 0, 0.07], [1, 1, 0.01],
    [0, -2, 0.05], [0, -1, 0]
]

# 아래로 갈 때 위치와 비율
d_rare = [
    [0, -2, 0.02], [0, 2, 0.02],
    [1, -1, 0.1], [0, -1, 0.07], [-1, -1, 0.01], [1, 1, 0.1], [0, 1, 0.07], [-1, 1, 0.01],
    [2, 0, 0.05], [1, 0, 0]
]

# 오른쪽으로 갈 때 위치와 비율
r_rate = [
    [-2, 0, 0.02], [2, 0, 0.02],
    [-1, -1, 0.01], [-1, 0, 0.07], [-1, 1, 0.1], [1, -1, 0.01], [1, 0, 0.07], [1, 1, 0.1],
    [0, 2, 0.05], [0, 1, 0]
]

# 위로 갈 때 위치와 비율
u_rate = [
    [0, -2, 0.02], [0, 2, 0.02],
    [-1, -1, 0.1], [0, -1, 0.07], [1, -1, 0.01], [-1, 1, 0.1], [0, 1, 0.07], [1, 1, 0.01],
    [-2, 0, 0.05], [-1, 0, 0]
]

# 원하는 방향으로 cnt 만큼 반복하여 이동
def move(cnt, idx, t):
    global sx, sy
    for _ in range(cnt + 1):
        sx += dx[idx]
        sy += dy[idx]

        # (0, 0) 지점에 도달하는 경우 종료
        if sx < 0 or sy < 0:
            break

        tornado(t)


# 이동 후 모래 날리기
def tornado(t):
    global result
    remove_sand = 0  # 비율에 따라 날아간 먼지의 합

    if t == 'l':
        rate = l_rate
    elif t == 'r':
        rate = r_rate
    elif t == 'd':
        rate = d_rare
    elif t == 'u':
        rate = u_rate

    for x, y, r in rate:
        # 먼지가 날아가는 위치 구하기
        nx = sx + x
        ny = sy + y

        if r == 0:  # 알파 구역에 날린 먼지 구하기
            s = sand[sx][sy] - remove_sand
        else:  # 비율에 따라 날린 먼지 구하기
            s = int(sand[sx][sy] * r)

        # 모래밭 범위 내로 먼지가 날린 경우
        if 0 <= nx < n and 0 <= ny < n:
            sand[nx][ny] += s  # 기존 위치의 먼지 + 날아온 먼지
        else:
            result += s  # 범위 밖으로 나간 먼지는 최종 값에 추가

        remove_sand += s  # 날린 먼지의 합구하기


n = int(stdin.readline())
sand = []
for _ in range(n):
    sand.append(list(map(int, stdin.readline().split())))

sx = n // 2
sy = n // 2

result = 0

for i in range(n):
    if i % 2 == 0:
        move(i, 0, 'l')
        move(i, 1, 'd')
    else:
        move(i, 2, 'r')
        move(i, 3, 'u')

print(result)

 

자바 코드는 다음과 같습니다.

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

public class Main {
    private static int[] dx = {0, 1, 0, -1};
    private static int[] dy = {-1, 0, 1, 0};

    // 왼쪽으로 이동할 때 날리는 먼지의 위치와 비율을 Rate 클래스로 저장
    private static Rate[] leftRate = {
            new Rate(-2, 0, 0.02), new Rate(2, 0, 0.02),
            new Rate(-1, -1, 0.1), new Rate(-1, 0, 0.07), new Rate(-1, 1, 0.01),
            new Rate(1, -1, 0.1), new Rate(1, 0, 0.07), new Rate(1, 1, 0.01),
            new Rate(0, -2, 0.05), new Rate(0, -1, 0)
    };

    // 아래로 이동할 때 날리는 먼지의 위치와 비율을 Rate 클래스로 저장
    private static Rate[] downRate = {
            new Rate(0, -2, 0.02), new Rate(0, 2, 0.02),
            new Rate(1, -1, 0.1), new Rate(0, -1, 0.07), new Rate(-1, -1, 0.01),
            new Rate(1, 1, 0.1), new Rate(0, 1, 0.07), new Rate(-1, 1, 0.01),
            new Rate(2, 0, 0.05), new Rate(1, 0, 0)
    };

    // 오른쪽으로 이동할 때 날리는 먼지의 위치와 비율을 Rate 클래스로 저장
    private static Rate[] rightRate = {
            new Rate(-2, 0, 0.02), new Rate(2, 0, 0.02),
            new Rate(-1, -1, 0.01), new Rate(-1, 0, 0.07), new Rate(-1, 1, 0.1),
            new Rate(1, -1, 0.01), new Rate(1, 0, 0.07), new Rate(1, 1, 0.1),
            new Rate(0, 2, 0.05), new Rate(0, 1, 0)
    };

    // 위로 이동할 때 날리는 먼지의 위치와 비율을 Rate 클래스로 저장
    private static Rate[] upRate = {
            new Rate(0, -2, 0.02), new Rate(0, 2, 0.02),
            new Rate(-1, -1, 0.1), new Rate(0, -1, 0.07), new Rate(1, -1, 0.01),
            new Rate(-1, 1, 0.1), new Rate(0, 1, 0.07), new Rate(1, 1, 0.01),
            new Rate(-2, 0, 0.05), new Rate(-1, 0, 0)
    };

    private static int n;
    private static int[][] sand;

    // 마법사 상어의 위치
    private static int sx;
    private static int sy;

    // 범위 밖으로 날린 먼지의 합
    private static int result = 0;

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

        n = Integer.parseInt(br.readLine());
        sand = new int[n][n];
        for (int i = 0; i < n; i++) {
            sand[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        sx = n / 2;
        sy = n / 2;

        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                move(i, 0);
                move(i, 1);
            } else {
                move(i, 2);
                move(i, 3);
            }
        }

        System.out.println(result);
    }

    // 토네이도 형태로 이동하기
    private static void move(int count, int idx) {
        for (int i = 0; i < count + 1; i++) {
            sx += dx[idx];
            sy += dy[idx];

            // (0, 0) 지점까지 이동한 경우
            if (sx < 0 || sy < 0) {
                break;
            }

            // 각 방향에 맞게 사용할 비율 배열 전달
            switch (idx) {
                case 0:
                    tornado(leftRate);
                    break;
                case 1:
                    tornado(downRate);
                    break;
                case 2:
                    tornado(rightRate);
                    break;
                case 3:
                    tornado(upRate);
                    break;
            }

        }
    }

    // 이동한 위치를 기준으로 모래 날리기
    private static void tornado(Rate[] rates) {
        int removeSand = 0;
        for (Rate rate : rates) {
            // 모래가 날릴 위치 구하기
            int nx = sx + rate.x;
            int ny = sy + rate.y;

            int rs = 0;
            if (rate.rate == 0) {  // 알파 구역에 날릴 모래 구하기
                rs = sand[sx][sy] - removeSand;
            } else {  // 비율에 따라 날린 모래 구하기
                rs = (int) (sand[sx][sy] * rate.rate);
            }

            // 모래밭 범위 내로 먼지가 날린 경우
            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                sand[nx][ny] += rs;  // 기존 먼지 + 날린 먼지
            } else {
                result += rs;  // 밖으로 날린 먼지 추가
            }

            removeSand += rs;  // 비율에 따라 날린 먼지의 합
        }

    }

    // 먼지가 날릴 위치와 해당 위치로 날릴 먼지의 비율을 나타내는 클래스
    private static class Rate {
        int x;
        int y;
        double rate;

        public Rate(int x, int y, double rate) {
            this.x = x;
            this.y = y;
            this.rate = rate;
        }
    }
}