[백준 - G3] 20057. 마법사 상어와 토네이도

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

 

 

문제 풀이

1. 격자의 중심인 (r/2, c/2) 좌표부터 (좌, 하, 우, 상) 반시계 방향으로 회전한다.

• 길이가 1인 회전을 2번하면 길이가 2인 회전을 2번하게 된다.

gemini가 그려준 먼가 디자인 요상한 그림

2. 회전을 하면 모래가 흩날려야 하는데, 아래의 회전공식을 통해 비율에 맞게 흩날릴 수 있게 한다.

3. 남은 모래값은 a에 넣고, 범위를 벗어나는 모래들의 합이 정답이므로 answer에 모두 더한다.

 

 

 

[회전 공식]

회전	공식
90도	(dx, dy) → (-dy, dx)
180도	(dx, dy) → (-dx, -dy)
270도	(dx, dy) → (dy, -dx)

 

예시

 

 

 

전체 코드

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

class Pair {
	int x, y;

	Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

class Spread {
	int dx, dy, percent;

	Spread(int dx, int dy, int percent) {
		this.dx = dx;
		this.dy = dy;
		this.percent = percent;
	}
}

/*
 * ratio도 방향에 따라 회전을 해야함.
 * 
 */
public class Main {

	static int[][] map;
	static int n;
	static int answer = 0;

	static Spread[] ratio = { new Spread(-2, 0, 2), new Spread(-1, -1, 10), new Spread(-1, 0, 7), new Spread(-1, 1, 1),
			new Spread(0, -2, 5), new Spread(1, -1, 10), new Spread(1, 0, 7), new Spread(1, 1, 1),
			new Spread(2, 0, 2) };

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());

		map = new int[n][n];
		for (int i = 0; i < n; i++) {
			String[] split = br.readLine().split(" ");
			for (int j = 0; j < n; j++) {
				map[i][j] = Integer.parseInt(split[j]);
			}
		}

		int sx = n / 2, sy = n / 2;

		move(sx, sy);
		System.out.println(answer);
	}

	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { -1, 0, 1, 0 };

	static void move(int x, int y) {

		boolean[][] visited = new boolean[n][n];
		visited[x][y] = true;

		int dir = 0;
		int len = 1;
		while (true) {

			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < len; j++) {
					x += dx[dir];
					y += dy[dir];

					// 토네이도 진행
					storm(x, y, dir);

					if (x == 0 && y == 0)
						return;

				}
				dir = (dir + 1) % 4;
			}

			len++;

		}

	}

	static void storm(int x, int y, int dir) {

		// 비율 별로 모래가 흩날린다

		int sand = map[x][y];
		int totalMoved = 0;

		for (Spread spread : ratio) {

			int nx = 0, ny = 0;

			switch (dir) {
			case 0: {
				nx = x + spread.dx;
				ny = y + spread.dy;
				break;
			}
			case 1: {
				nx = x - spread.dy;
				ny = y + spread.dx;
				break;
			}

			case 2: {
				nx = x - spread.dx;
				ny = y - spread.dy;
				break;
			}
			case 3: {
				nx = x + spread.dy;
				ny = y - spread.dx;
				break;
			}
			}

			int moved = (int) (sand * spread.percent / 100);
			totalMoved += moved;

			if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
				answer += moved;
			} else {
				map[nx][ny] += moved;
			}

		}

		int ax = x + dx[dir];
		int ay = y + dy[dir];
		int alpha = sand - totalMoved;

		if (ax < 0 || ay < 0 || ax >= n || ay >= n) {
			answer += alpha;
		} else {
			map[ax][ay] += alpha;
		}

	}
}

 

📡 Link

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