Algorithm/Problem
마법사 상어와 토네이도(BJ_G3_20057)
당진개발자
2024. 2. 25. 14:43
1. 문제 링크
https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
2. 나의 코드
메모리: 84288kb
시간: 588ms
코드 길이: 4315B
시간 복잡도 : O(N^2)
설명
- 상하좌우 이동 시 확인해야 하는 곳을 따로 함수로 구현
- 맵 밖으로 나가면 result에 더하면서 달팽이 모양으로 탐색import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ_20057 {
// 좌 하 우 상
static int[] dr = {0, 1, 0, -1};
static int[] dc = {-1, 0, 1, 0};
static int N, nowR, nowC, result;
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i< N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
nowR = N / 2; nowC = N / 2;
solve();
System.out.println(result);
}
private static void solve() {
int d = 0; // 이동 방향
int s = 1; // 이동 거리
while (true) {
for (int i = 0; i < 2; i++) {
for (int j = 0; j < s; j++) {
if (nowR == 0 && nowC == 0) return; // 만약 시작 지점으로 돌아 왔으면 끝내기
int nr = nowR + dr[d];
int nc = nowC + dc[d];
switch (d) {
case 0:
left(nr, nc, d);
break;
case 1:
down(nr, nc, d);
break;
case 2:
right(nr, nc, d);
break;
case 3:
up(nr, nc, d);
break;
}
nowR = nr;
nowC = nc;
}
d = (d + 1) % 4; // 방향 바꾸기
}
++s; // 이동 거리 늘려주기
}
}
private static boolean isValid (int r, int c) {
return 0 <= r && r < N && 0 <= c && c < N;
}
// 왼쪽으로 이동 시
private static void left(int r, int c, int d) {
int[] dx = {-2, -1, -1, -1, 0, 1, 1, 1, 2};
int[] dy = {0, -1, 0, 1, -2, -1, 0, 1, 0};
double[] percent = {2.0, 10.0, 7.0, 1.0, 5.0, 10.0, 7.0, 1.0, 2.0};
check(r, c, d, dx, dy, percent);
}
// 아래쪽으로 이동 시
private static void down(int r, int c, int d) {
int[] dx = {-1, -1, 0, 0, 0, 0, 1, 1, 2};
int[] dy = {-1, 1, -2, -1, 1, 2, -1, 1, 0};
double[] percent = {1, 1, 2, 7, 7, 2, 10, 10, 5};
check(r, c, d, dx, dy, percent);
}
// 오른쪽으로 이동 시
private static void right(int r, int c, int d) {
int[] dx = {-2, -1, -1, -1, 0, 1, 1, 1, 2};
int[] dy = {0, -1, 0, 1, 2, -1, 0, 1, 0};
double[] percent = {2, 1, 7, 10, 5, 1, 7, 10, 2};
check(r, c, d, dx, dy, percent);
}
// 위쪽으로 이동 시
private static void up(int r, int c, int d) {
int[] dx = {-2, -1, -1, 0, 0, 0, 0, 1, 1};
int[] dy = {0, -1, 1, -2, -1, 1, 2, -1, 1};
double[] percent = {5, 10, 10, 2, 7, 7, 2, 1, 1};
check(r, c, d, dx, dy, percent);
}
private static void check(int r, int c, int d, int[] dx, int[] dy, double[] percent) {
int moveSand = 0;
for (int i = 0; i < 9; i++) {
int nr = r + dx[i];
int nc = c + dy[i];
int value = (int) Math.floor(map[r][c] * percent[i] / 100.0); // 이동 할 모래의 값
if (isValid(nr, nc)) {
map[nr][nc] += value;
moveSand += value;
} else {
result += value;
moveSand += value;
}
}
int nr = r + dr[d];
int nc = c + dc[d];
// 만약 격자 밖으로 나가지 않았다면
if (isValid(nr, nc)) {
map[nr][nc] += map[r][c] - moveSand;
} else {
result += map[r][c] - moveSand;
}
map[r][c] = 0;
}
}
3. 정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, answer;
// 9시 방향부터 반시계 방향
static int[] dr = {0, 1, 1, 1, 0, -1, -1, -1};
static int[] dc = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
play();
System.out.println(answer);
}
// 토네이도 시전
private static void play() {
// 토네이도의 위치와 방향
int r = N / 2;
int c = N / 2;
int dir = 0;
int s;
for (s = 1; s < N; s++) {
// 이동해야하는 칸수만큼 반복
for (int i = 0; i < s * 2; i++) {
// 방향 전환
if (i == s) {
dir = (dir + 2) % 8;
}
r += dr[dir];
c += dc[dir];
blowSand(r, c, dir);
}
// 방향 전환
dir = (dir + 2) % 8;
}
for (int i = 0; i < s - 1; i++) {
r += dr[dir];
c += dc[dir];
blowSand(r, c, dir);
}
}
// 모래를 흩날리게 하는 기능을 가진 메서드
private static void blowSand(int r, int c, int dir) {
int sand = map[r][c];
int blowedSand = 0;
int nr;
int nc;
int nDir;
for (int i = 0; i < 8; i++) {
nDir = (dir + i) % 8;
if (i == 0) {
nr = r + 2 * dr[nDir];
nc = c + 2 * dc[nDir];
if (!isIn(nr, nc)) {
answer += sand * 0.05;
} else {
map[nr][nc] += sand * 0.05;
}
blowedSand += sand * 0.05;
} else if (i == 1 || i == 7) {
nr = r + dr[nDir];
nc = c + dc[nDir];
if (!isIn(nr, nc)) {
answer += sand * 0.1;
} else {
map[nr][nc] += sand * 0.1;
}
blowedSand += sand * 0.1;
} else if (i == 2 || i == 6) {
nr = r + dr[nDir];
nc = c + dc[nDir];
if (!isIn(nr, nc)) {
answer += sand * 0.07;
} else {
map[nr][nc] += sand * 0.07;
}
blowedSand += sand * 0.07;
nr = r + 2 * dr[nDir];
nc = c + 2 * dc[nDir];
if (!isIn(nr, nc)) {
answer += sand * 0.02;
} else {
map[nr][nc] += sand * 0.02;
}
blowedSand += sand * 0.02;
} else if (i == 3 || i == 5) {
nr = r + dr[nDir];
nc = c + dc[nDir];
if (!isIn(nr, nc)) {
answer += sand * 0.01;
} else {
map[nr][nc] += sand * 0.01;
}
blowedSand += sand * 0.01;
}
}
nr = r + dr[dir];
nc = c + dc[dir];
if (!isIn(nr, nc)) {
answer += sand - blowedSand;
} else {
map[nr][nc] += sand - blowedSand;
}
map[r][c] = 0;
}
private static boolean isIn(int r, int c) {
return r >= 0 && c >= 0 && r < N && c < N;
}
}
4. 배운 점
- 구현 문제는 처음에 잘 못 만들면 디버깅이 어렵다.
- 처음에 설계를 잘하자.