N x N의 필드가 있으며 필드는 1 x 1 크기의 칸들로 이루어져 있다. 각각의 칸에는 물을 저장할 수 있는 바구니들이 배치되어 있다. 마법사 상어는 비바라기 마법을 시험해보자 한다. 비바라기 마법은 N x N 필드의 좌측 하단에 비구름 4개를 생성한다. (N, 1) (N, 2) (N-1, 1) (N-1, 2)에 배치된다. 마법사 상어는 비바라기 마법을 통해 4개의 구름을 생성한 뒤 M번의 명령을 실행하고자 한다. 한 번의 명령은 다음과 같이 진행된다.
마법사 상어는 방향(1 ~ 8)과 거리(1 ~ 50)를 명령한다.
구름들은 명령에 따라 해당 방향으로 주어진 거리만큼 이동한다.
필드는 마법을 통해 무한으로 연결되어 있다.
필드의 경계는 반대쪽 경계와 이어진다.
구름에서 비가 내린다.
동일한 위치에 있는 바구니에 물이 1만큼 채워진다.
비를 내린 구름은 사라진다.
물 복사가 이루어진다.
물 복사는 3번을 통해 물의 양이 늘어난 바구니에서만 발생한다.
물 복사는 물이 1이라도 있는 대각선 방향의 바구니 개수만큼 복사되어 현재 바구니에 채워진다.
다만, 경계를 넘어서 있는 대각선 바구니는 고려하지 않는다. (N, N) 바구니는 (N-1, N-1) 바구니만 고려한다.
바구니에서 물이 증발하여 구름이 생성된다.
구름이 생성되기 위해서는 바구니에 2 이상의 물이 있어야 한다
구름이 생성되면 물이 2 감소한다.
다만, 3번에서 비가 내린 바구니에서는 구름이 생성되지 못한다.
모든 명령이 끝나고 필드 바구니들에 있는 물의 총량을 구한다.
각각의 명령은 다음과 같이 처리된다.
public void command(int directionNo, int distance) {
Queue<Basket> increasedBaskets = new PriorityQueue<>();
Direction direction = Direction.getDirection(directionNo);
while (!clouds.isEmpty()) {
Cloud cloud = clouds.poll();
cloud.move(direction, distance, SIZE);
increasedBaskets.offer(cloud.rain(baskets));
}
for (Basket basket : increasedBaskets) basket.copyWater(baskets);
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
Basket basket = baskets[row][col];
if (baskets[row][col].equals(increasedBaskets.peek())) increasedBaskets.poll();
else if (basket.hasEnoughWater(2)) clouds.offer(basket.createCloud());
}
}
}
increasedBaskets들은 비가 내린 바구니들이다. 물 복사와 구름 생성 시 이에 대한 정보가 필요하기 때문에 사용한다. 주어진 방향 정보에 맞게 Direction을 생성한다. 이후 현재 생성되어 있는 구름들을 움직이고 비를 내리게 한다. 구름들이 모두 움직이고 비가 내리면 비가 추가된 바구니들을 탐색하며 물을 복사한다. 물 복사가 완료되면 전체 바구니들을 탐색하며 물이 2 이상 있는 바구니에서 구름을 생성한다. 다만, 비가 내렸던 바구니는 구름을 생성하지 않는다.
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
final int SIZE = Integer.parseInt(tokenizer.nextToken()); // 필드의 가로 세로 크기
int commandNum = Integer.parseInt(tokenizer.nextToken()); // 명령 횟수
Field field = new Field(SIZE); // 마법을 시험해보는 필드
// 필드의 각 칸마다 바구니 추가
for (int row = 0; row < SIZE; row++) {
tokenizer = new StringTokenizer(reader.readLine());
for (int col = 0; col < SIZE; col++)
field.addBasket(row, col, Integer.parseInt(tokenizer.nextToken()));
}
// 비바라기 마법을 시전하여 좌측 하단에 4개의 구름 생성
field.createCloud(SIZE - 1, 0);
field.createCloud(SIZE - 1, 1);
field.createCloud(SIZE - 2, 0);
field.createCloud(SIZE - 2, 1);
// 마법을 시전하면서 명령
while (commandNum-- > 0) {
tokenizer = new StringTokenizer(reader.readLine());
int directionNo = Integer.parseInt(tokenizer.nextToken()); // 이동 방향 번호
int distance = Integer.parseInt(tokenizer.nextToken()); // 이동 거리
field.command(directionNo, distance); // 명령
}
// 필드 바구니들의 물 총량
result.append(field.collectWater());
public class Field {
private final int SIZE; // 가로 세로 크기
private final Basket[][] baskets; // 각 칸의 바구니
private final Queue<Cloud> clouds = new LinkedList<>(); // 현재 생성되어 있는 구름
public Field(int size) {
SIZE = size;
baskets = new Basket[SIZE][SIZE];
}
/**
* 상어 마법사의 명령을 처리한다.
* @param directionNo 이동 방향 번호
* @param distance 이동 거리
*/
public void command(int directionNo, int distance) {
Queue<Basket> increasedBaskets = new PriorityQueue<>(); // 비가 내린 바구니 우선순위 큐
Direction direction = Direction.getDirection(directionNo); // 이동 방향
// 각 구름들은 이동하고 비를 내린 후 소멸
while (!clouds.isEmpty()) {
Cloud cloud = clouds.poll(); // 사실상 구름 소멸 역할
cloud.move(direction, distance, SIZE); // 구름 이동
increasedBaskets.offer(cloud.rain(baskets)); // 구름에서 비내리기
}
// 비가 내린 바구니들에서 물 복사 시전
for (Basket basket : increasedBaskets) basket.copyWater(baskets);
// 비가 내리지 않은 바구니들에서 물이 충분하다면 구름 생성
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
Basket basket = baskets[row][col];
// 비가 내린 바구니이면 구름 미생성
if (baskets[row][col].equals(increasedBaskets.peek())) increasedBaskets.poll();
// 비가 내리지 않고 물이 충분하다면 구름 생성
else if (basket.hasEnoughWater(2)) clouds.offer(basket.createCloud());
}
}
}
/**
* 구름을 생성한다.
* @param row 구름 생성 위치 row
* @param col 구름 생성 위치 column
*/
public void createCloud(int row, int col) {
clouds.offer(new Cloud(row, col));
}
/**
* 바구니를 추가한다.
* @param row 바구니 추가 위치 row
* @param col 바구니 추가 위치 column
* @param water 바구니의 초기 물의 양
*/
public void addBasket(int row, int col, int water) {
baskets[row][col] = new Basket(row, col, water);
}
/**
* 필드 바구니들의 물의 총합을 구한다.
* @return 물의 총합
*/
public int collectWater() {
int amountOfWater = 0;
for (int row = 0; row < SIZE; row++)
for (int col = 0; col < SIZE; col++)
amountOfWater += baskets[row][col].getWater();
return amountOfWater;
}
}
public class Basket implements Comparable<Basket> {
private final int ROW, COL; // 바구니의 위치
private int water; // 바구니에 담긴 물의 양
public Basket(int row, int col, int water) {
this.ROW = row;
this.COL = col;
this.water = water;
}
/**
* 물이 담긴 주변 바구니의 개수만큼 물을 복사한다.
* @param baskets 필드 바구니들
*/
public void copyWater(Basket[][] baskets) {
// 대각 방향에 있는 바구니들을 탐색하며 현재 바구니에 물을 추가한다.
for (int d = 2; d <= 8; d += 2) { // d = 2, 4, 6, 8 = NW, NE, SE, SW
Direction direction = Direction.getDirection(d); // 대각 바구니 방향
try {
Basket basket = baskets[ROW + direction.row()][COL + direction.col()]; // 대각 바구니
if (basket.hasEnoughWater(1)) addWater(1); // 대각 바구니에 물이 있으면 물 복사
} catch (ArrayIndexOutOfBoundsException ignore) { // 경계를 벗어나면 무시
}
}
}
/**
* 바구니에 물을 추가한다.
* @param water 추가하고자 하는 물의 양
*/
public void addWater(int water) {
this.water += water;
}
/**
* 물이 어느 정도 이상 있는지 확인하다.
* @param water 확인하고자하는 물의 양
* @return 물이 충분히 있는지에 대한 여부
*/
public boolean hasEnoughWater(int water) {
return this.water >= water;
}
/**
* 바구니에 있는 물을 통해 구름을 생성한다.
* @return 생성된 구름
*/
public Cloud createCloud() {
water -= 2;
return new Cloud(ROW, COL);
}
/**
* 바구니에 담긴 물의 양을 확인한다.
* @return 물의 양
*/
public int getWater() {
return water;
}
/**
* 왼쪽 위에 있는 바구니가 우선순위를 가진다.
* @param b the object to be compared.
* @return 우선순위 비교 결과
*/
@Override
public int compareTo(Basket b) {
return ROW == b.ROW ? COL - b.COL : ROW - b.ROW;
}
}
public class Cloud {
private int row, col; // 구름의 위치
public Cloud(int row, int col) {
this.row = row;
this.col = col;
}
/**
* 구름을 이동시킨다.
* @param direction 이동 방향
* @param distance 이동 거리
* @param limit 경계값
*/
public void move(Direction direction, int distance, int limit) {
row += direction.row() * distance;
col += direction.col() * distance;
if (row >= 0) row %= limit;
else while (row < 0) row += limit;
if (col >= 0) col %= limit;
else while (col < 0) col += limit;
}
/**
* 구름에서 비가 내린다.
* @param baskets 바구니 집합
* @return 비가 내린 바구니
*/
public Basket rain(Basket[][] baskets) {
baskets[row][col].addWater(1);
return baskets[row][col];
}
}
public enum Direction {
W(0, -1), NW(-1, -1), N(-1, 0), NE(-1, 1),
E(0, 1), SE(1, 1), S(1, 0), SW(1, -1);
private final int row, col;
Direction(int row, int col) {
this.row = row;
this.col = col;
}
public static Direction getDirection(int direction) {
return Direction.values()[direction - 1];
}
public int row() {
return row;
}
public int col() {
return col;
}
}