Java/코딩테스트
백준 20057
Bubbles
2023. 10. 12. 01:37
🌪 백준 20057 : 마법사 상어와 토네이도
https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
🌪 저번 글에 열받았다고 썼는데 플래그였던 것이다..... 얘가 더...더 힘들었다...
🌪 로직 자체는 토네이도 움직이기, 한 칸씩 움직일때마다 모래 날려주기 이렇게 2가지만 있다.
🌪 하지만 날아가는 각 모래를 모두 계산해줘야 하기 때문에 실수하기 쉽고, 어디서 틀렸는지 잘 안보여서 헤맨...문제이다.
🌪 토네이도의 회전을 보면 규칙이 있다.
🌪 왼쪽 1칸 -> 아래 1칸 -> 오른쪽 2칸 -> 위 2칸 ...
- 방향은 계속 좌 - 하 - 우 - 상으로 번갈아 반복된다.
- 대신, 방향이 2번 바뀌면 이동할 칸수가 +1 씩 증가된다.
🌪 그래서 기본 방향 배열은 좌 - 하 - 우 - 상 순서대로 선언해둔다.
- dirCount라는 변수로 계속 방향 바꾼 횟수를 세고, 이 변수가 2가되면 0으로 초기화한 뒤 이동해야하는 칸 수(moveAmount)를 늘려준다.
- 계속 한 칸씩 움직이면서, 모래가 있는 칸이라면(map[cx][cy] > 0) removeSand함수 호출을 통해 모래를 제거해준다.
- 그리고 움직이다가 원점에 도달하면, 반복문을 탈출하고 함수가 종료된다.
🌪 move() 메소드 코드
private static void move() {
int cx = n / 2;
int cy = n / 2;
int dir = 0;
int dirCount = 0; // dirCount = 2면 움직여야 하는 양이 1씩 증가
int moveAmount = 1;
int moveCount = 0;
while (true) {
if (cx == 0 && cy == 0) {
break; // 원점 도착시 토네이도는 소멸
}
cx = cx + dirX[dir];
cy = cy + dirY[dir];
if (map[cx][cy] != 0) {
removeSand(new Pos(cx,cy), dir);
}
moveCount++;
if (moveAmount == moveCount) {
moveCount = 0;
dir = (dir + 1) % 4;
dirCount++;
}
if (dirCount == 2) {
dirCount = 0;
moveAmount++;
}
}
}
🌪 모래 제거
이건 이 모래를 열심히 구현하면 되긴 하는데, 여기서 바로 저 α 칸에 0.55를 넣으면 안되고, 각 칸에 모래를 다 나눠주고 나머지를 마지막에 빼줘야 답이 나온다... 소수점 버림 때문인지 쨌든 이것도 이 문제를 까다롭게 만들었다;
private static void removeSand(Pos pos, int dir) {
int removed = 0;
// 5%
int nextX = pos.x + dirX[dir] * 2;
int nextY = pos.y + dirY[dir] * 2;
if (isValid(nextX, nextY)) {
map[nextX][nextY] += map[pos.x][pos.y] * 5 / 100;
} else {
answer += map[pos.x][pos.y] * 5 / 100;
}
removed += map[pos.x][pos.y] * 5 / 100;
// 10% x는 그대로, y만 바뀌는것
nextX = pos.x + dirX[dir];
nextY = pos.y + dirY[dir];
for (int i = 1; i <= 3; i+=2) {
int nx = nextX + dirX[(dir+i)%4];
int ny = nextY + dirY[(dir+i)%4];
if (isValid(nx, ny)) {
map[nx][ny] += map[pos.x][pos.y] * 10 / 100;
} else {
answer += map[pos.x][pos.y] * 10 / 100;
}
removed += map[pos.x][pos.y] * 10 / 100;
}
// 2%, 7% : 현재 보는 방향의 좌 / 우이므로 +1, +3씩 더한다음 방향 재조정
// 방향 조정 : (dir + i) % 4
for (int i = 1; i <= 3; i+=2) {
for (int j = 1; j <= 2; j++) { // 7%는 1칸, 2%는 2칸
int nx = pos.x + dirX[(dir+i) % 4] * j;
int ny = pos.y + dirY[(dir+i) % 4] * j;
if (j == 1) {
if (isValid(nx, ny)) {
map[nx][ny] += map[pos.x][pos.y] * 7 / 100;
} else {
answer += map[pos.x][pos.y] * 7 / 100;
}
removed += map[pos.x][pos.y] * 7 / 100;
} else {
if (isValid(nx, ny)) {
map[nx][ny] += map[pos.x][pos.y] * 2 / 100;
} else {
answer += map[pos.x][pos.y] * 2 / 100;
}
removed += map[pos.x][pos.y] * 2 / 100;
}
}
}
// 1%
nextX = pos.x - dirX[dir];
nextY = pos.y - dirY[dir];
for (int i = 1; i <= 3; i+=2) {
int nx = nextX + dirX[(dir+i)%4];
int ny = nextY + dirY[(dir+i)%4];
if (isValid(nx, ny)) {
map[nx][ny] += map[pos.x][pos.y] / 100;
} else {
answer += map[pos.x][pos.y] / 100;
}
removed += map[pos.x][pos.y]/ 100;
}
nextX = pos.x + dirX[dir];
nextY = pos.y + dirY[dir];
if (isValid(nextX, nextY)) {
map[nextX][nextY] += map[pos.x][pos.y] - removed;
} else {
answer += map[pos.x][pos.y] - removed;
}
map[pos.x][pos.y] = 0;
}
🌪 전체코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class p20057 {
static int n, answer;
static int[][] map;
static int[] dirX = { 0, 1, 0, -1 }; // 좌하우상
static int[] dirY = { -1, 0, 1, 0 };
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
answer = 0;
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
move();
System.out.println(answer);
}
private static void move() {
int cx = n / 2;
int cy = n / 2;
int dir = 0;
int dirCount = 0; // dirCount = 2면 움직여야 하는 양이 1씩 증가
int moveAmount = 1;
int moveCount = 0;
while (true) {
if (cx == 0 && cy == 0) {
break; // 원점 도착시 토네이도는 소멸
}
cx = cx + dirX[dir];
cy = cy + dirY[dir];
if (map[cx][cy] != 0) {
removeSand(new Pos(cx,cy), dir);
}
moveCount++;
if (moveAmount == moveCount) {
moveCount = 0;
dir = (dir + 1) % 4;
dirCount++;
}
if (dirCount == 2) {
dirCount = 0;
moveAmount++;
}
}
}
private static void removeSand(Pos pos, int dir) {
int removed = 0;
// 5%
int nextX = pos.x + dirX[dir] * 2;
int nextY = pos.y + dirY[dir] * 2;
if (isValid(nextX, nextY)) {
map[nextX][nextY] += map[pos.x][pos.y] * 5 / 100;
} else {
answer += map[pos.x][pos.y] * 5 / 100;
}
removed += map[pos.x][pos.y] * 5 / 100;
// 10% x는 그대로, y만 바뀌는것
nextX = pos.x + dirX[dir];
nextY = pos.y + dirY[dir];
for (int i = 1; i <= 3; i+=2) {
int nx = nextX + dirX[(dir+i)%4];
int ny = nextY + dirY[(dir+i)%4];
if (isValid(nx, ny)) {
map[nx][ny] += map[pos.x][pos.y] * 10 / 100;
} else {
answer += map[pos.x][pos.y] * 10 / 100;
}
removed += map[pos.x][pos.y] * 10 / 100;
}
// 2%, 7% : 현재 보는 방향의 좌 / 우이므로 +1, +3씩 더한다음 방향 재조정
// 방향 조정 : (dir + i) % 4
for (int i = 1; i <= 3; i+=2) {
for (int j = 1; j <= 2; j++) { // 7%는 1칸, 2%는 2칸
int nx = pos.x + dirX[(dir+i) % 4] * j;
int ny = pos.y + dirY[(dir+i) % 4] * j;
if (j == 1) {
if (isValid(nx, ny)) {
map[nx][ny] += map[pos.x][pos.y] * 7 / 100;
} else {
answer += map[pos.x][pos.y] * 7 / 100;
}
removed += map[pos.x][pos.y] * 7 / 100;
} else {
if (isValid(nx, ny)) {
map[nx][ny] += map[pos.x][pos.y] * 2 / 100;
} else {
answer += map[pos.x][pos.y] * 2 / 100;
}
removed += map[pos.x][pos.y] * 2 / 100;
}
}
}
// 1%
nextX = pos.x - dirX[dir];
nextY = pos.y - dirY[dir];
for (int i = 1; i <= 3; i+=2) {
int nx = nextX + dirX[(dir+i)%4];
int ny = nextY + dirY[(dir+i)%4];
if (isValid(nx, ny)) {
map[nx][ny] += map[pos.x][pos.y] / 100;
} else {
answer += map[pos.x][pos.y] / 100;
}
removed += map[pos.x][pos.y]/ 100;
}
nextX = pos.x + dirX[dir];
nextY = pos.y + dirY[dir];
if (isValid(nextX, nextY)) {
map[nextX][nextY] += map[pos.x][pos.y] - removed;
} else {
answer += map[pos.x][pos.y] - removed;
}
map[pos.x][pos.y] = 0;
}
private static boolean isValid(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n) {
return false;
}
return true;
}
static class Pos {
int x;
int y;
Pos (int x, int y) {
this.x = x;
this.y = y;
}
}
}