📌 Problem
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부터 차례대로 W, NW, NE, E, SE, S, SW 방향이다.
-
구름들은 명령에 따라 해당 방향으로 주어진 거리만큼 이동한다.
-
필드는 마법을 통해 무한으로 연결되어 있다.
-
필드의 경계는 반대쪽 경계와 이어진다.
-
-
구름에서 비가 내린다.
-
동일한 위치에 있는 바구니에 물이 1만큼 채워진다.
-
비를 내린 구름은 사라진다.
-
-
물 복사가 이루어진다.
-
물 복사는 3번을 통해 물의 양이 늘어난 바구니에서만 발생한다.
-
물 복사는 물이 1이라도 있는 대각선 방향의 바구니 개수만큼 복사되어 현재 바구니에 채워진다.
-
다만, 경계를 넘어서 있는 대각선 바구니는 고려하지 않는다. (N, N) 바구니는 (N-1, N-1) 바구니만 고려한다.
-
-
바구니에서 물이 증발하여 구름이 생성된다.
-
구름이 생성되기 위해서는 바구니에 2 이상의 물이 있어야 한다
-
구름이 생성되면 물이 2 감소한다.
-
다만, 3번에서 비가 내린 바구니에서는 구름이 생성되지 못한다.
-
모든 명령이 끝나고 필드 바구니들에 있는 물의 총량을 구한다.
📌 Solution
각각의 명령은 다음과 같이 처리된다.
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 이상 있는 바구니에서 구름을 생성한다. 다만, 비가 내렸던 바구니는 구름을 생성하지 않는다.
📌 Code
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;
}
}
Hello, Devs!