[ BOJ ] 20057 마법사 상어와 토네이도 G3 삼성 기출 (JAVA)

---

---

 

20057번: 마법사 상어와 토네이도

문제 이해

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다. 토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.       토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다. 토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다. 토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

아이디어

- 시뮬은 하라는 대로 . - 토네이도는 이동할 때 좌 - 하 - 우 - 상 방향을 반복한다. - 토네이도는 특정 방향으로 이동 시 1,1,2,2,...,N-1,N-1,N번 그 방향으로 이동한다. - 방향 별 비율의 규칙을 찾았다. 좌를 기준으로 2차원 배열을 만들었다. 코드를 참고. - 퍼센트는 방향별로 순서가 같기 때문에 1차원 배열로 만들었다. - y는 모든 계산이 끝나면 0이된다. - 0,0 (배열기준)에 도착하면 토네이도를 끝낸다. - 소멸하는 값은 비율과 알파값이 있다.

코드

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

public class Main {
	static class Pos {
		int x, y;
		Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int N, map[][], sum=0;
	static Pos start;
	static int[][] dir = { { 0, 1, 0, -1 }, { -1, 0, 1, 0 } }; // 좌 하 우 상 으로 움직임.
	// 좌, 하(y*-1,x반대로), 우(x,y*-1), 상(y,x반대로)
	static int[][] tor = { { 0, -1, 1, -2, -1, 1, 2, -1, 1 }, { -2, -1, -1, 0, 0, 0, 0, 1, 1 } }; 
	static double[] percent = { 0.05, 0.1, 0.1, 0.02, 0.07, 0.07, 0.02, 0.01, 0.01 };
	static int[][] alphaDir = { { 0, 1, 0, -1 }, { -1, 0, 1, 0 } };
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		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());
			}
		}
		process(); // 토네이도 처리
		System.out.println(sum);
	}

	static void process() {
		start = new Pos(N / 2, N / 2); // 시작 위치
		int len = 1, cnt =0; // 1,1,2,2,3,3,...,N,N
		while(true) {
			if(start.x==0 && start.y==0) break;
			for (int d = 0; d < 4; ++d) {
				for(int i=0;i<len;++i) {
					if(start.x==0 && start.y==0) break;
					int nx = start.x + dir[0][d];
					int ny = start.y + dir[1][d];
					if (isBoundary(nx, ny)) {
						// 방향에따라 처리한다.
						tornaido(d, nx, ny);
						start.x = nx;
						start.y= ny;
					}
				}
				if(++cnt==2) {
					++len;
					cnt=0;
				}
			}
		}
	}

	static void tornaido(int d, int x, int y) {
		int alpha = map[x][y];// a 값을 계산하기 위함
		for (int t = 0; t < 9; ++t) {
			int torx =0,tory=0;
			if(d==0) {
				torx=tor[0][t];
				tory=tor[1][t];
			}else if(d==1) {
				torx=tor[1][t]*-1;
				tory=tor[0][t];
			}else if(d==2) {
				torx=tor[0][t];
				tory=tor[1][t]*-1;
			}else if(d==3) {
				torx=tor[1][t];
				tory=tor[0][t];
			}
			int nx = x + torx;
			int ny = y + tory;
			int val = (int)(map[x][y] * percent[t]); // 모래 비율을 계산한다.
			alpha -= val; // 사용된 값은 빼준다.
			if (isBoundary(nx, ny)) {
				map[nx][ny] += val;
			}else sum+=val;
		}
		// y기준으로 알파값을 갱신해준다.
		if(isBoundary(x+alphaDir[0][d],y+alphaDir[1][d]))
			map[x + alphaDir[0][d]][y + alphaDir[1][d]] += alpha;
		else sum+=alpha;
		map[x][y]=0;//y위치의 모래는사라진다.
	}

	static boolean isBoundary(int x, int y) { // 범위 검사.
		return 0 <= x && x < N && 0 <= y && y < N;
	}

}

 

---

 

CPDM