![[BOJ/JAVA] 마법사 상어와 토네이도](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FnQrzj%2FbtrRCZbOo7D%2F6b5BMrLOLC4pTTfiZXSMVk%2Fimg.jpg)
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
키워드
다음은 토네이도의 이동 경로이다.
다음은 x→y로 이동할 때 y의 모래의 이동 비율이다.
계산에서 소수점 아래는 버린다.
구현
중요한 것은 a의 값이 55%가 아니라는 것이다.
계산에서 소수점 아래는 버리는 연산을 하므로, 흩뿌려진 모래값을 전부 뺀 뒤에 남은 값이 a가 된다는 것이다.
- 처음엔 토네이도를 달팽이처럼 이동시키는 알고리즘을 작성한다.
- 다음으로 수평, 수직에 따라 모래를 흩뿌리는 알고리즘을 작성한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class java_20057 {
final static int dydx[][] = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
static int board[][];
static int N;
static int result;
static int tmp = 0;
static void printBoard() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] + "\\t");
}
System.out.println();
}
}
// 흩날리기
static void spread(int y, int x, int moveIndex) {
int toY = y + dydx[moveIndex][0];
int toX = x + dydx[moveIndex][1];
// System.out.printf("To toY : %d, toX : %d\\n", toY, toX);
// toY, toX의 모래를 거리가 2인 위치에 전부 뿌린다.
// 방향은 moveIndex 방향이다.
// 수평 방향인지 수직 방향인지 판단하자.
// 모래는 board[toY][toX] 기준
int leftSand = board[toY][toX];
// 수평 방향이다.
if (moveIndex % 2 == 0) {
// 1% 더하기 -> x 기준 y+-1
try {
board[toY + 1][x] += board[toY][toX] / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] / 100;
}
leftSand -= board[toY][toX] / 100;
try {
board[toY - 1][x] += board[toY][toX] / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] / 100;
}
leftSand -= board[toY][toX] / 100;
// 7% 더하기 -> toX 기준 y+-1
try {
board[y + 1][toX] += board[toY][toX] * 7 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 7 / 100;
}
leftSand -= board[toY][toX] * 7 / 100;
try {
board[y - 1][toX] += board[toY][toX] * 7 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 7 / 100;
}
leftSand -= board[toY][toX] * 7 / 100;
// 2% 더하기 -> toX 기준 y+-2
try {
board[y + 2][toX] += board[toY][toX] * 2 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 2 / 100;
}
leftSand -= board[toY][toX] * 2 / 100;
try {
board[y - 2][toX] += board[toY][toX] * 2 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 2 / 100;
}
leftSand -= board[toY][toX] * 2 / 100;
// 10% 더하기 -> toX+dydx[moveIndex][1] 기준 y+-1
try {
board[y + 1][toX + dydx[moveIndex][1]] += board[toY][toX] * 10 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 10 / 100;
}
leftSand -= board[toY][toX] * 10 / 100;
try {
board[y - 1][toX + dydx[moveIndex][1]] += board[toY][toX] * 10 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 10 / 100;
}
leftSand -= board[toY][toX] * 10 / 100;
// 5% 더하기 -> toX + (dydx[moveIndex][1] * 2)
try {
board[y][toX + (dydx[moveIndex][1] * 2)] += board[toY][toX] * 5 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 5 / 100;
}
leftSand -= board[toY][toX] * 5 / 100;
// 55% 더하기 -> toX+dydx[moveIndex][1]
try {
board[y][toX + dydx[moveIndex][1]] += leftSand;
} catch (ArrayIndexOutOfBoundsException e) {
result += leftSand;
}
}
// 수직 방향이다.
else {
// 1% 더하기 -> y 기준 x+-1
try {
board[y][x + 1] += board[toY][toX] / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] / 100;
}
leftSand -= board[toY][toX] / 100;
try {
board[y][x - 1] += board[toY][toX] / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] / 100;
}
leftSand -= board[toY][toX] / 100;
// 7% 더하기 -> toY 기준 x+-1
try {
board[toY][x + 1] += board[toY][toX] * 7 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 7 / 100;
}
leftSand -= board[toY][toX] * 7 / 100;
try {
board[toY][x - 1] += board[toY][toX] * 7 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 7 / 100;
}
leftSand -= board[toY][toX] * 7 / 100;
// 2% 더하기 -> toY 기준 x+-2
try {
board[toY][x + 2] += board[toY][toX] * 2 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 2 / 100;
}
leftSand -= board[toY][toX] * 2 / 100;
try {
board[toY][x - 2] += board[toY][toX] * 2 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 2 / 100;
}
leftSand -= board[toY][toX] * 2 / 100;
// 10% 더하기 -> toY+dydx[moveIndex][0] 기준 x+-1
try {
board[toY + dydx[moveIndex][0]][x + 1] += board[toY][toX] * 10 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 10 / 100;
}
leftSand -= board[toY][toX] * 10 / 100;
try {
board[toY + dydx[moveIndex][0]][x - 1] += board[toY][toX] * 10 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 10 / 100;
}
leftSand -= board[toY][toX] * 10 / 100;
// 5% 더하기 -> toY + (dydx[moveIndex][0] * 2)
try {
board[toY + (dydx[moveIndex][0] * 2)][x] += board[toY][toX] * 5 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 5 / 100;
}
leftSand -= board[toY][toX] * 5 / 100;
// 55% 더하기 -> toY+dydx[moveIndex][0]
try {
board[toY + dydx[moveIndex][0]][x] += leftSand;
} catch (ArrayIndexOutOfBoundsException e) {
result += leftSand;
}
}
// 모래 이동했으므로 0이 된다.
board[toY][toX] = 0;
}
// 이동하기
static void solution() {
int y = board.length / 2;
int x = board.length / 2;
int moveCount = 0;
int moveIndex = 0;
int length = 1;
while (true) {
// 길이 증가
if (moveCount == 2) {
moveCount = 0;
length++;
}
for (int i = 0; i < length; i++) {
// System.out.printf("From y : %d x : %d\\n", y, x);
// 흩뿌리기
spread(y, x, moveIndex);
y += dydx[moveIndex][0];
x += dydx[moveIndex][1];
// printBoard();
if (y == 0 && x == 0) {
return;
}
}
// 방향 변경
moveCount++;
moveIndex = (moveIndex + 1) % dydx.length;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
//
board = new int[N][N];
result = 0;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
solution();
System.out.println(result);
br.close();
}
}
키워드
다음은 토네이도의 이동 경로이다.
다음은 x→y로 이동할 때 y의 모래의 이동 비율이다.
계산에서 소수점 아래는 버린다.
구현
중요한 것은 a의 값이 55%가 아니라는 것이다.
계산에서 소수점 아래는 버리는 연산을 하므로, 흩뿌려진 모래값을 전부 뺀 뒤에 남은 값이 a가 된다는 것이다.
- 처음엔 토네이도를 달팽이처럼 이동시키는 알고리즘을 작성한다.
- 다음으로 수평, 수직에 따라 모래를 흩뿌리는 알고리즘을 작성한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class java_20057 {
final static int dydx[][] = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } };
static int board[][];
static int N;
static int result;
static int tmp = 0;
static void printBoard() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(board[i][j] + "\\t");
}
System.out.println();
}
}
// 흩날리기
static void spread(int y, int x, int moveIndex) {
int toY = y + dydx[moveIndex][0];
int toX = x + dydx[moveIndex][1];
// System.out.printf("To toY : %d, toX : %d\\n", toY, toX);
// toY, toX의 모래를 거리가 2인 위치에 전부 뿌린다.
// 방향은 moveIndex 방향이다.
// 수평 방향인지 수직 방향인지 판단하자.
// 모래는 board[toY][toX] 기준
int leftSand = board[toY][toX];
// 수평 방향이다.
if (moveIndex % 2 == 0) {
// 1% 더하기 -> x 기준 y+-1
try {
board[toY + 1][x] += board[toY][toX] / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] / 100;
}
leftSand -= board[toY][toX] / 100;
try {
board[toY - 1][x] += board[toY][toX] / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] / 100;
}
leftSand -= board[toY][toX] / 100;
// 7% 더하기 -> toX 기준 y+-1
try {
board[y + 1][toX] += board[toY][toX] * 7 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 7 / 100;
}
leftSand -= board[toY][toX] * 7 / 100;
try {
board[y - 1][toX] += board[toY][toX] * 7 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 7 / 100;
}
leftSand -= board[toY][toX] * 7 / 100;
// 2% 더하기 -> toX 기준 y+-2
try {
board[y + 2][toX] += board[toY][toX] * 2 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 2 / 100;
}
leftSand -= board[toY][toX] * 2 / 100;
try {
board[y - 2][toX] += board[toY][toX] * 2 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 2 / 100;
}
leftSand -= board[toY][toX] * 2 / 100;
// 10% 더하기 -> toX+dydx[moveIndex][1] 기준 y+-1
try {
board[y + 1][toX + dydx[moveIndex][1]] += board[toY][toX] * 10 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 10 / 100;
}
leftSand -= board[toY][toX] * 10 / 100;
try {
board[y - 1][toX + dydx[moveIndex][1]] += board[toY][toX] * 10 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 10 / 100;
}
leftSand -= board[toY][toX] * 10 / 100;
// 5% 더하기 -> toX + (dydx[moveIndex][1] * 2)
try {
board[y][toX + (dydx[moveIndex][1] * 2)] += board[toY][toX] * 5 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 5 / 100;
}
leftSand -= board[toY][toX] * 5 / 100;
// 55% 더하기 -> toX+dydx[moveIndex][1]
try {
board[y][toX + dydx[moveIndex][1]] += leftSand;
} catch (ArrayIndexOutOfBoundsException e) {
result += leftSand;
}
}
// 수직 방향이다.
else {
// 1% 더하기 -> y 기준 x+-1
try {
board[y][x + 1] += board[toY][toX] / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] / 100;
}
leftSand -= board[toY][toX] / 100;
try {
board[y][x - 1] += board[toY][toX] / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] / 100;
}
leftSand -= board[toY][toX] / 100;
// 7% 더하기 -> toY 기준 x+-1
try {
board[toY][x + 1] += board[toY][toX] * 7 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 7 / 100;
}
leftSand -= board[toY][toX] * 7 / 100;
try {
board[toY][x - 1] += board[toY][toX] * 7 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 7 / 100;
}
leftSand -= board[toY][toX] * 7 / 100;
// 2% 더하기 -> toY 기준 x+-2
try {
board[toY][x + 2] += board[toY][toX] * 2 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 2 / 100;
}
leftSand -= board[toY][toX] * 2 / 100;
try {
board[toY][x - 2] += board[toY][toX] * 2 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 2 / 100;
}
leftSand -= board[toY][toX] * 2 / 100;
// 10% 더하기 -> toY+dydx[moveIndex][0] 기준 x+-1
try {
board[toY + dydx[moveIndex][0]][x + 1] += board[toY][toX] * 10 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 10 / 100;
}
leftSand -= board[toY][toX] * 10 / 100;
try {
board[toY + dydx[moveIndex][0]][x - 1] += board[toY][toX] * 10 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 10 / 100;
}
leftSand -= board[toY][toX] * 10 / 100;
// 5% 더하기 -> toY + (dydx[moveIndex][0] * 2)
try {
board[toY + (dydx[moveIndex][0] * 2)][x] += board[toY][toX] * 5 / 100;
} catch (ArrayIndexOutOfBoundsException e) {
result += board[toY][toX] * 5 / 100;
}
leftSand -= board[toY][toX] * 5 / 100;
// 55% 더하기 -> toY+dydx[moveIndex][0]
try {
board[toY + dydx[moveIndex][0]][x] += leftSand;
} catch (ArrayIndexOutOfBoundsException e) {
result += leftSand;
}
}
// 모래 이동했으므로 0이 된다.
board[toY][toX] = 0;
}
// 이동하기
static void solution() {
int y = board.length / 2;
int x = board.length / 2;
int moveCount = 0;
int moveIndex = 0;
int length = 1;
while (true) {
// 길이 증가
if (moveCount == 2) {
moveCount = 0;
length++;
}
for (int i = 0; i < length; i++) {
// System.out.printf("From y : %d x : %d\\n", y, x);
// 흩뿌리기
spread(y, x, moveIndex);
y += dydx[moveIndex][0];
x += dydx[moveIndex][1];
// printBoard();
if (y == 0 && x == 0) {
return;
}
}
// 방향 변경
moveCount++;
moveIndex = (moveIndex + 1) % dydx.length;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
//
board = new int[N][N];
result = 0;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
solution();
System.out.println(result);
br.close();
}
}
'Coding Test > BOJ' 카테고리의 다른 글
| [BOJ/JAVA] 20208번: 진우의 민트초코우유 (0) | 2022.11.27 |
|---|---|
| [BOJ/JAVA] 2580번: 스도쿠 (0) | 2022.11.27 |
| [BOJ/JAVA] 3190번: 뱀 (0) | 2022.11.21 |
| [BOJ/JAVA] 23351번: 물주기 (0) | 2022.11.21 |
| [BOJ/JAVA] 10709번: 기상캐스터 (0) | 2022.11.21 |