[백준/자바] 20057 마법사 상어와 토네이도

https://www.acmicpc.net/problem/20057

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

---

문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다.

위치 (r, c)는 격자의 r행 c열을 의미하고, A [r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 

토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다.

비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다.

α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다.

모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다.

위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 

모래가 격자의 밖으로 이동할 수도 있다.

토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다.

r번째 줄에서 c번째 주어지는 정수는 A [r][c]이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

제한

• 3 ≤ N ≤ 499
• N은 홀수
• 0 ≤ A [r][c] ≤ 1,000
• 가운데 칸에 있는 모래의 양은 0

예제 입력 1

5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0

예제 출력 1 

10

예제 입력 2 

5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0

예제 출력 2 

85

예제 입력 3 

7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 0 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7

예제 출력 3 

139

예제 입력 4 

5
100 200 300 400 200
300 243 432 334 555
999 111 0 999 333
888 777 222 333 900
100 200 300 400 500

예제 출력 4 

7501

예제 입력 5 

5
0 0 100 0 0
0 0 100 0 0
0 0 0 0 0
0 0 100 0 0
0 0 100 0 0

예제 출력 5 

283

예제 입력 6 

9
193 483 223 482 858 274 847 283 748
484 273 585 868 271 444 584 293 858
828 384 382 818 347 858 293 999 727
818 384 727 373 636 141 234 589 991
913 564 555 827 0 999 123 123 123
321 321 321 983 982 981 983 980 990
908 105 270 173 147 148 850 992 113
943 923 982 981 223 131 222 913 562
752 572 719 590 551 179 141 137 731

예제 출력 6 

22961

---

설명

구현 문제인데 문제를 잘못 이해해 한참 헤맨 문제다.

토네이도가 연습하는 크기가 N×N인 격자로 나누어진 모래밭 = sand [][]

움직이는 방향 = dxy [][] = {{0,-1}, {1,0}, {0,1}, {-1,0}}; // (0: 서쪽, 1:남쪽, 2:동쪽, 3:북쪽

토네이도가 이동했을 때 움직이는 모래의 위치 = ArrayList <point>[] tornado

 

가장 먼저 토네이도가 나선형 모양으로 회전하는 함수를 살펴보자.

sx와 sy는 각각 토네이도가 시작하는 행과 열의 위치를 나타낸다.

tx와 ty는 토네이도가 이동한 행과 열의 위치를 나타낸다.

토네이도가 나선형을 도는 것을 살펴보면 개수가 증가하면서 서쪽&남쪽, 동쪽&북쪽 쌍으로 움직이는 것을 알 수 있다.

아래 그림처럼 같은 개수만큼 쌍으로 움직이는 것을 시각적으로 확인 가능하다.

움직이는 방향이 dxy [][] = {{0,-1}, {1,0}, {0,1}, {-1,0}}; // (0: 서쪽, 1:남쪽, 2:동쪽, 3:북쪽으로 지정했기 때문에

움직이는 수가 홀수면 서쪽&남쪽 짝수면 동쪽&북쪽로 지정하면 된다.

이때 (0,0)에 도착하면 마지막 n만큼 돌지 않고 토네이도가 멈추는 조건 역시 추가해야 한다.

static void move() {
	int sx = n/2;
	int sy = n/2;
	int tx = sx;
	int ty = sy;

	for(int i = 0; i < n; i++) { // 토네이도의 길이
		int ind = 0;
		if (i%2 == 1) ind = 2;
		for(int j = 0; j < 2; j++, ind++) { // 토네이도 길이는 2개씩 움직인다. 서쪽&남쪽, 동쪽&북쪽
			for(int k = 0; k < i+1; k++) {
				tx += dxy[ind][0];
				ty += dxy[ind][1];
				if(tx < 0 || n <= tx || ty < 0 || n <= ty) continue; 
				makeTornado(tx, ty, ind);
				if(tx == 0 && ty == 0) return;
			}
		}
	} 
}

 

다음은 토네이도가 움직였을 때 흩날리는 모래의 양을 구하는 함수를 살펴보자.

다음 그림은 x위치에서 y 위치로 토네이도가 움직였을 때 흩어지는 모래 양에 대한 그림이다.

처음 착각했던 것이 x에서 y로 움직이면서 x에 있던 모래 양이 y 위치에 모두 더해지는 것으로 생각했다.

그러면 어마어마한 결괏값이 나오므로 생략하도록 한다.

 x위치에서 y 위치로 토네이도가 움직일 뿐 모래는 움직이지 않는다는 것을 유의해야 한다.

또한 a의 값은 55%가 아니라는 것을 알아야 한다.

해당 값은 다른 모래의 양을 구해 꼭 y의 원래 양에서 감소한 양으로 구해야 한다.

먼저 point라는 class를 통해 y 위치와 떨어진 모래의 위치와 비율을 저장하는 tornado라는 변수를 지정한다.

static class point{
	int d; // 방향
	int r; // 비율
		
	point(int d, int r){
		this.d = d;
		this.r = r;
	}
}

이때 초기값으로 세팅된 값에 대해 설명하겠다.

 

먼저 움직이는 방향에 따라 다르겠지만 움직이는 방향을 주축, 그에 수직인 방향을 수직축으로 지칭하겠다.

tornado변수의 위치에 해당하는 변수 값은 주축을 움직이는 양이라고 생각하면 되고

해당 위치의 point.d의 값은 수직축을 움직이는 양이라고 생각하면 된다.

 

움직이는 방향이 서쪽이라고 가정해보자.

그렇다면 주축은 열의 값이 변하는 y축이 될 것이고 수직축은 행의 값이 변하는 x축이 될 것이다.

tornado[0]. add(new point(1,1)); 가 의미하는 값은

주축은 0만큼

수직축은 1만큼 이동한 위치의 모래 양은 1%라는 것을 의미한다.

이때 의문이 들어야 정상인데 왜냐하면 해당 위치는 아래 그림에서 빨간색 위치지 파란색 위치가 아니기 때문이다.

여기서 주축은 위치에 해당하는 변숫값 -1 만큼 움직이면 되겠구나 생각하면 된다.

그렇게 해서 수직축이 0 이상일 경우는 좌우대칭으로 움직이면 되겠다는 생각이 들것이다.

 

다음 내용을 코드로 구현하면 다음과 같다.

 

주축을 y축으로 하는 경우는 서쪽으로 움직이거나 동쪽으로 움직이는 경우이며

x축으로 하는 경우는 북쪽이나 남쪽으로 움직이는 경우로 이를 check 변수를 이용해 지정한다.

static ArrayList<point>[] tornado = new ArrayList[4];

tornado[0].add(new point(1,1));
tornado[1].add(new point(1,7));
tornado[1].add(new point(2,2));
tornado[2].add(new point(0,-1));
tornado[2].add(new point(1,10));
tornado[3].add(new point(0,5));

// 모래 흩날림
static void makeTornado(int x, int y, int d) {
	HashMap<Integer, Integer> hm = new HashMap<>();
	hm.put(1, (int)(sand[x][y]*0.01));
	hm.put(2, (int)(sand[x][y]*0.02));
	hm.put(5, (int)(sand[x][y]*0.05));
	hm.put(7, (int)(sand[x][y]*0.07));
	hm.put(10, (int)(sand[x][y]*0.1));
	int nam = sand[x][y] - 2*(hm.get(1) + hm.get(2) + hm.get(7) + hm.get(10)) - hm.get(5);
	hm.put(-1, nam);
	sand[x][y] = 0;
	boolean check = false; // 서쪽  or 동쪽 : false
	if(d == 1 || d == 3) check = true; // 남쪽  or 북쪽 :  true
			
	for(int i = 0; i < 4; i++) {
		for(point cur : tornado[i]) {
			int tx = 0;
			int ty = 0;
			if(!check) {  // 서쪽  or 동쪽 : false
				tx = x + cur.d;
				ty = y + dxy[d][1]*(i-1);
			}else {  // 남쪽  or 북쪽 :  true
				tx = x + dxy[d][0]*(i-1);
				ty = y + cur.d;
			}
				
			if(cur.d == 0) { // 흩날리는 모래가 대칭이 아닌 경우
				if(tx < 0 || n <= tx || ty < 0 || n <= ty) total += hm.get(cur.r);
				else sand[tx][ty] += hm.get(cur.r);
			}else { // 흩날리는 모래가 대칭인 경우
				if(check) {
					if(tx < 0 || n <= tx || ty < 0 || n <= ty) total += hm.get(cur.r);
					else sand[tx][ty] += hm.get(cur.r);
						
					ty = y - cur.d;
						
					if(tx < 0 || n <= tx || ty < 0 || n <= ty) total += hm.get(cur.r);
					else sand[tx][ty] += hm.get(cur.r);
				}else {
					if(tx < 0 || n <= tx || ty < 0 || n <= ty) total += hm.get(cur.r);
					else sand[tx][ty] += hm.get(cur.r);
						
					tx = x - cur.d;
						
					if(tx < 0 || n <= tx || ty < 0 || n <= ty) total += hm.get(cur.r);
					else sand[tx][ty] += hm.get(cur.r);
				}
			}
		}
	}
}

코드