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

leehyunjon·2022년 6월 15일

boj 구현 시뮬레이션

Algorithm

목록 보기

70/162

20057 마법사 상어와 토네이도 : https://www.acmicpc.net/problem/20057

Problem

Solve

또 문제의 조건을 완벽히 이해못해서 시간이 걸린 문제되겠다..

이번에 놓친 조건은 알파로 이동하는 모래의 양은 이동하지 않은 남은 모래의 양이라는 조건을 놓쳤다. 그냥 기존 모래의 55%를 이동시켜주고 있었다..

이 문제의 핵심은 이동하는 모래를 주어진 위치에 이동시키는것이다.

이동시켜줄 위치별로 기존 모래에서 이동할 좌표를 설정해준다.

//행 이동
static int[][] sy = {{-1, 1, -2, -1, 1, 2, -1, 1, 0}, {-1, -1, 0, 0, 0, 0, 1, 1, 2},
		{1, -1, 2, 1, -1, -2, 1, -1, 0}, {1, 1, 0, 0, 0, 0, -1, -1, -2}};
//열 이동
static int[][] sx = {{1, 1, 0, 0, 0, 0, -1, -1, -2}, {-1, 1, -2, -1, 1, 2, -1, 1, 0}, {-1, -1, 0, 0, 0, 0, 1, 1, 2},
		{1, -1, 2, 1, -1, -2, 1, -1, 0}};
//각 이동할 비율
static int[] sandRatio = {1, 1, 2, 7, 7, 2, 10, 10, 5};

그런 다음 각 이동할 좌표에 ([기존 모래] * sandRatio[i] ) / 100를 이동시켜주고
알파 자리에는 [기존 모래] - [이동한 모래]를 이동시켜준다.

그리고 토네이도는 나선으로 회전하는데 1,1,2,2,3,3,4,4 ... 으로 규칙적으로 이동하는 칸 수가 증가하므로 유의하며 구현하면 된다.

Code

public class 마법사상어와토네이도 {
	static int N;
	static int[][] map;
	static int outSand;

	static int[] dy = {0, 1, 0, -1};
	static int[] dx = {-1, 0, 1, 0};
	static int[][] sy = {{-1, 1, -2, -1, 1, 2, -1, 1, 0}, {-1, -1, 0, 0, 0, 0, 1, 1, 2},
		{1, -1, 2, 1, -1, -2, 1, -1, 0}, {1, 1, 0, 0, 0, 0, -1, -1, -2}};
	static int[][] sx = {{1, 1, 0, 0, 0, 0, -1, -1, -2}, {-1, 1, -2, -1, 1, 2, -1, 1, 0}, {-1, -1, 0, 0, 0, 0, 1, 1, 2},
		{1, -1, 2, 1, -1, -2, 1, -1, 0}};
	static int[] sandRatio = {1, 1, 2, 7, 7, 2, 10, 10, 5};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		map = new int[N][N];

		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());
			}
		}

		//모래밭 밖으로 나간 모래의 양
		outSand = 0;
		start();
		bw.write(String.valueOf(outSand));
		bw.flush();
		bw.close();
	}

	static void start() {
		int y = N / 2;
		int x = N / 2;

		int move = 1;
		int count = 0;
		int dir = 0;
		while (true) {

			//해당 방향으로 move만큼 이동한다.
			for (int i = 1; i <= move; i++) {
				y += dy[dir];
				x += dx[dir];

				//(0,0)에서 모래를 이동시킨 후 함수는 종료된다.
				if(y<0 || x<0 || y>=N || x>=N) return;

				//모래 이동
				spraySand(dir, y, x);

			}

			//서로 다른 방향으로 2번씩 이동할때마다 이동하는 거리가 +1씩 증가한다.
			if (++count == 2) {
				move++;
				count = 0;
			}
            //방향은 무한 반복
			dir = (dir + 1) % 4;
		}
	}

	static void spraySand(int dir, int y, int x) {
		int totalSpraySand = 0;
        //총 9곳으로 모래의 이동
		for (int i = 0; i < 9; i++) {
			int ny = y + sy[dir][i];
			int nx = x + sx[dir][i];
			int sand = map[y][x];
            //해당 좌표로 이동할 모래
			int spraySand = (sand * sandRatio[i])/100;
			if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
				map[ny][nx] += spraySand;
			} else {
				outSand += spraySand;
			}
            //이동한 모래의 총 개수
			totalSpraySand += spraySand;
		}

		//알파로 이동
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		int sand = map[y][x];
        //알파로 이동할 모래
		int spreadSand = sand - totalSpraySand;
		if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
			map[ny][nx] += spreadSand;
		}else{
			outSand += spreadSand;
		}

		map[y][x] = 0;
	}
}