[BOJ 20057] 마법사 상어와 토네이도

문제

• BOJ 20057
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

1. 달팽이 숫자로 map을 탐색한다.
   • 그림을 그려보면 이동 칸수가 dist이고 1 1 2 2 3 3… 씩 하나씩 증가하면서 2번 반복한 후 방향이 바뀌는 것을 알 수 있다. 예외적으로 마지막 dist일 때는 3번 반복되므로 한번 더 해준다. 이를 이용해 다음 좌표를 구하고 이동시킨다.

2. move(int dist)에서 dist만큼 반복해서 현재 방향으로 이동한다.

3. 모래를 흩날리기 위해 spread(int nx, int ny)를 호출한다.
   • 현재 총 모래양을 total에 저장하고, 각 비율 별 뿌려야할 모래양, 나머지양을 변수에 저장한다.
   • 현재 방향에 따라 넣어줘야할 비율의 좌표를 구하고, check(int x, int y)에서 범위 체크 후 이를 만족하면 해당 좌표 map[nx][ny]에 amount를 누적해준다.
   • 격자 밖인 경우에 답이 되므로 Ans에 누적해준다.
   • 좌표는 현재 방향이 좌,우일때 같고 상,하일때 같은 점을 이용해 구한다.
4. 1,1까지 오면 탐색종료 후 Ans를 출력한다.

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N;
	static int[][] map; // 모래양 저장
	static int[][] dArr = { { 0, -1 }, { 1, 0 }, { 0, 1 }, { -1, 0 } }; // 좌하우상
	static int nowX, nowY, nowD; // 현재 좌표, 방향
	static int Ans; // 격자밖으로 나간 모래양

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		map = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} // End input

		// 시작점 구하기
		nowX = (N + 1) / 2;
		nowY = (N + 1) / 2;
		nowD = 0;

		// 달팽이숫자로 이동 시작
		int dist = 1;
		boolean flag = true;
		while (flag) {
			for (int cnt = 0; cnt < 2; cnt++) { // 2번 반복
				move(dist);
				
				if(nowX == 1 && nowY == N) {
					move(dist);
					flag = false;
					break;
				}
			}
			dist++;
		}
		
		System.out.println(Ans);
	}

	private static void move(int dist) {
		for (int k = 0; k < dist; k++) { // 이동칸 수
			int nx = nowX + dArr[nowD][0];
			int ny = nowY + dArr[nowD][1];
			spread(nx, ny); // 모래 흩날리기
			nowX = nx;
			nowY = ny;
		}
		nowD = (nowD + 1) % 4;
	}

	private static void check(int nx, int ny, int amt) {
		if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) map[nx][ny] += amt;
		else Ans += amt; // 격자밖
	}

	private static void spread(int nx, int ny) {
		int total = map[nx][ny]; // 총 모래 양
		map[nx][ny] = 0;
		
		int amt1 = (int) (total * 0.01); // 2번 넣음
		int amt2 = (int) (total * 0.02); // 2번
		int amt5 = (int) (total * 0.05); // 1번
		int amt7 = (int) (total * 0.07); // 2번
		int amt10 = (int) (total * 0.1); // 2번
		int a = total - 2 * (amt1 + amt2 + amt7 + amt10) - amt5;// 나머지 양(알파에 넣을 양) = total에서 amt1~10뺀거
		int ax = nx + dArr[nowD][0];
		int ay = ny + dArr[nowD][1];

		if (nowD == 0 || nowD == 2) { // 좌우
			// 1%
			check(nowX - 1, nowY, amt1);
			check(nowX + 1, nowY, amt1);

			// 7%
			check(nx - 1, ny, amt7);
			check(nx + 1, ny, amt7);

			// 2%
			check(nx - 2, ny, amt2);
			check(nx + 2, ny, amt2);

			// 10%
			check(ax - 1, ay, amt10);
			check(ax + 1, ay, amt10);

			// 5%
			check(ax + dArr[nowD][0], ay + dArr[nowD][1], amt5);
		} else if (nowD == 1 || nowD == 3) { // 상하
			// 1%
			check(nowX, nowY - 1, amt1);
			check(nowX, nowY + 1, amt1);

			// 7%
			check(nx, ny - 1, amt7);
			check(nx, ny + 1, amt7);

			// 2%
			check(nx, ny - 2, amt2);
			check(nx, ny + 2, amt2);

			// 10%
			check(ax, ay - 1, amt10);
			check(ax, ay + 1, amt10);

			// 5%
			check(ax + dArr[nowD][0], ay + dArr[nowD][1], amt5);
		}
		
		check(ax, ay, a);
	}
}