https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
문제를 보고 경우의 수들을 생각하고 재귀를 이용하면 간단히 풀릴거라고 생각했다.
빨리 풀고 넘어가야겠다고 생각하고 시작했지만 생각보다 오래걸렸다...
int[][] dx = {{-1, -1, -2, -1, 0, 1, 1, 2, 1, 0}
, {0, 1, 1, 2, 3, 2, 1, 1, 0, 1}
, {1, 1, 2, 1, 0, -1, -1, -2, -1, 0}
, {0, -1, -1, -2, -3, -2, -1, -1, 0, -1}};
int[][] dy = {{0, -1, -1, -2, -3, -2, -1, -1, 0, -1}
, {-1, -1, -2, -1, 0, 1, 1, 2, 1, 0}
, {0, 1, 1, 2, 3, 2, 1, 1, 0, 1}
, {1, 1, 2, 1, 0, -1, -1, -2, -1, 0}};
int[] dz = {1, 7, 2, 10, 5, 10, 7, 2, 1};먼저 위에 사진에 보이는 좌표들을 순서대로 순환하기 위한 이차원 배열들을 만든다.
dx와 dy는 각각 확인할 좌표로 가기 위한 이동하기 위한 값들이다.
추가로, dx와 dy 마지막 수는 이동할 y의 좌표이다.
즉, dx와 dy의 0번째 부터 8번째 까지는 1번 부터 9번 좌표, 9번째는 y좌표를 뜻한다.
나눠도 되겠지만 그냥 같이 넣어놨다.
dz는 이동할 좌표의 비율이다.
int temp; //날아간 양
int xx, yy; //날아갈 위치
for (int q = 0; q < cnt; q++) {
temp = 0;
if (x == 0 && y == 0)
return;
for (int i = 0; i < 9; i++) {
xx = x + dx[dir][i];
yy = y + dy[dir][i];
int send = map[x + dx[dir][9]][y + dy[dir][9]] * dz[i] / 100;
if (xx >= 0 && xx < N && yy >= 0 && yy < N) {
map[xx][yy] += send;
temp += send;
} else {
temp += send;
}
}send는 현재 확인하는 좌표로 얼마만큼 날아가지는 계산한다. 어차피 소수점은 버린다고 했으니 정수형으로 선언했다.
날아갈 위치가 범위 안이라면 모래를 합쳐준다.
temp는 a로 날아갈 양을 확인하기 위해 얼만큼 날아가는지 저장한다.
그냥 55퍼센트로 하면 될까 싶었지만 버림으로 인해 양이 다를것 같아 그냥 temp에 저장했다.
switch (dir) {
case 0: //왼
if (x >= 0 && x < N && y - 2 >= 0 && y - 2 < N)
map[x][y - 2] += (map[x][y - 1] - temp); //a로 날아감
map[x][y - 1] = 0;
y--;
break;
case 1: //아래
if (x + 2 >= 0 && x + 2 < N && y >= 0 && y < N)
map[x + 2][y] += (map[x + 1][y] - temp); //a로 날아감
map[x + 1][y] = 0;
x++;
break;
case 2: //오
if (x >= 0 && x < N && y + 2 >= 0 && y + 2 < N)
map[x][y + 2] += (map[x][y + 1] - temp); //a로 날아감
map[x][y + 1] = 0;
y++;
break;
case 3: //위
if (x - 2 >= 0 && x - 2 < N && y >= 0 && y < N)
map[x - 2][y] += (map[x - 1][y] - temp); //a로 날아감
map[x - 1][y] = 0;
x--;
break;
}
}dir은 현재 방향이다. 방향에 따라 a로 날아가는 좌표를 다르게 해 남은 모래를 날려주고 x혹은 y 좌표를 바꿔준다.
switch (dir) {
case 0: //왼
to(1, cnt);
break;
case 1: //아래
to(2, cnt + 1);
break;
case 2: //오
to(3, cnt);
break;
case 3: //위
to(0, cnt + 1);
break;
}현재 방향에 맞게 재귀호출, 위 사진을 보면
아래 방향에서 오른쪽 방향으로 바뀌거나 위 방향에서 왼쪽 방향으로 바뀔 때마다 이동 횟수가 1씩 증가하는걸 볼 수 있어 두 경우에만 cnt + 1을 해준다.
전체코드
import java.util.Scanner;
public class Main {
static int[][] map;
static int result, x, y;
static int N, mid;
static void to(int dir, int cnt) { //방향, 이동 횟수
int[][] dx = {{-1, -1, -2, -1, 0, 1, 1, 2, 1, 0}
, {0, 1, 1, 2, 3, 2, 1, 1, 0, 1}
, {1, 1, 2, 1, 0, -1, -1, -2, -1, 0}
, {0, -1, -1, -2, -3, -2, -1, -1, 0, -1}};
int[][] dy = {{0, -1, -1, -2, -3, -2, -1, -1, 0, -1}
, {-1, -1, -2, -1, 0, 1, 1, 2, 1, 0}
, {0, 1, 1, 2, 3, 2, 1, 1, 0, 1}
, {1, 1, 2, 1, 0, -1, -1, -2, -1, 0}};
int[] dz = {1, 7, 2, 10, 5, 10, 7, 2, 1};
int temp; //날아간 양
int xx, yy; //날아갈 위치
for (int q = 0; q < cnt; q++) { //cnt 만큼 반복
temp = 0;
if (x == 0 && y == 0)
return;
for (int i = 0; i < 9; i++) {
xx = x + dx[dir][i];
yy = y + dy[dir][i];
int send = map[x + dx[dir][9]][y + dy[dir][9]] * dz[i] / 100;
if (xx >= 0 && xx < N && yy >= 0 && yy < N) {
map[xx][yy] += send;
temp += send;
} else {
temp += send;
}
}
switch (dir) {
case 0: //왼
if (x >= 0 && x < N && y - 2 >= 0 && y - 2 < N)
map[x][y - 2] += (map[x][y - 1] - temp); //a로 날아감
map[x][y - 1] = 0;
y--;
break;
case 1: //아래
if (x + 2 >= 0 && x + 2 < N && y >= 0 && y < N)
map[x + 2][y] += (map[x + 1][y] - temp); //a로 날아감
map[x + 1][y] = 0;
x++;
break;
case 2: //오
if (x >= 0 && x < N && y + 2 >= 0 && y + 2 < N)
map[x][y + 2] += (map[x][y + 1] - temp); //a로 날아감
map[x][y + 1] = 0;
y++;
break;
case 3: //위
if (x - 2 >= 0 && x - 2 < N && y >= 0 && y < N)
map[x - 2][y] += (map[x - 1][y] - temp); //a로 날아감
map[x - 1][y] = 0;
x--;
break;
}
}
switch (dir) {
case 0: //왼
to(1, cnt);
break;
case 1: //아래
to(2, cnt + 1);
break;
case 2: //오
to(3, cnt);
break;
case 3: //위
to(0, cnt + 1);
break;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
mid = N / 2 + 1;
x = mid - 1;
y = x;
map = new int[N][];
for (int i = 0; i < N; i++) {
map[i] = new int[N];
for (int j = 0; j < N; j++) {
map[i][j] = sc.nextInt();
result += map[i][j];
}
}
to(0, 1);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
result -= map[i][j];
}
}
System.out.println(result);
}
}위에서 설명한 코드들을 for문을 이용해 cnt의 갯수만큼 반복시켜준다.
메인에서는 map을 입력받으면서 현재 총 모래 수를 구한다.
그 후 토네이도가 끝난 후의 모래 양을 구해서 빼주면 답이다.
'코테 > JAVA' 카테고리의 다른 글
| [백준 14502 / JAVA] 연구소 (0) | 2023.07.12 |
|---|---|
| [백준 19236 / JAVA] 청소년 상어 (0) | 2023.07.09 |
| [백준 17779 / JAVA] 게리맨더링 2 (0) | 2023.07.04 |
| [백준 15686/JAVA] 치킨 배달 (0) | 2023.07.02 |
| [백준 1074/JAVA] Z (0) | 2023.06.30 |