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

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

www.acmicpc.net/problem/20057

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

 

---

/* 문제 설명 */

토네이도가 움직이면서 모래를 일정한 비율로 흩날린다. 

이 때, 격자 밖으로 나간 모래의 양을 구하시오.

 

/* 해결 방안 */

전형적인 구현 문제로, 크게 두 단계로 나눌 수 있다.

1. 토네이도의 움직임을 구현하기

2. 흩날리는 모래를 계산하기

 

우선 1번(토네이도의 움직임)부터 구현하기위해,

토네이도의 움직임을 잘 살펴보면 규칙을 알아낼 수 있다.

 

ⓐ 토네이도는 '왼쪽-아래-오른쪽-위' 순서대로 움직인다.

ⓑ 각각 2번씩 같은 길이(1~N)로 움직이는데, 마지막은 범위를 벗어나게 된다.

다음은 2번 (흩날리는 모래)에 대해 구현해보자.

여기서 주의할 점은 "다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전해야 된다는 점"이다.

'왼쪽-아래-오른쪽-위', 총 4가지 방향으로 움직이니까 직접 다 돌려줘야하는데,

여기서 왼쪽과 오른쪽은 y축 대칭이고, 아래와 위는 X축 대칭이므로,

왼쪽과 아래 방향만 구해주고 -1를 곱해서 오른쪽과 위쪽을 처리해주자!

 

 

 

/* 구현 과정 */

1. 중앙(N/2, N/2)에서 토네이도를 움직이는 함수 func( )을 호출한다.

2. 토네이도는 step(1~N)만큼의 길이로 2번씩 움직이고, 방향(dir)은 좌-하-우-상 순서로 달라진다.

3. 토네이도가 움직일 때 마다, 흩날리는 모래를 구하기 위해 moveSand( )를 호출한다.

4. 오른쪽(dir = 2)은 왼쪽(dir = 0)과 Y축 대칭 관계이다.

    따라서 모래가 흩날리는 비율을 담은 배열인 ry의 값에 대해 -1을 곱해준다. 

    위쪽(dir = 3)은 아래쪽(dir = 1)과 X축 대칭 관계이다.

    따라서 모래가 흩날리는 비율을 담은 배열인 rx의 값에 대해 -1을 곱해준다. 

5. 밖으로 빠져나간 모래(ans), 흩날리게 된 모래의 총합(sum), 현재 흩날린 모래(now_sand), 남게 된 모래(arr[nx][ny])를 구한다. 

6. 토네이도가 이동하여 도착한 장소는 0이 되도록 하는 걸 잊지 말자.

 

/* 소스 코드 */

 

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define R 10
typedef long long ll;
typedef pair<int, int>pi;
typedef pair<int, pi>pii;

int n, arr[505][505], dir, ans;

//모래가 흩날리는 위치 (왼쪽 방향과 아래 쪽 방향)
int rx[][10] = { {-2,-1,-1,-1,0,1,1,1,2,0}, 
				{-1,-1,0,0,0,0,1,1,2,1} };
int ry[][10] = { {0,-1,0,1,-2,-1,0,1,0,-1},
				{-1,1,-2,-1,1,2,-1,1,0,0} };
           
//모래가 흩날리는 비율 (왼쪽 방향과 아래 쪽 방향)
int r[][10] = { {2,10,7,1,5,10,7,1,2,0},
				{1,1,2,7,7,2,10,10,5,0} };
                
//토네이도 이동방향
int dx[] = { 0,1,0,-1 };
int dy[] = { -1,0,1,0 };

bool outrange(int x, int y) {
	if (x < 0 || y < 0 || x >= n || y >= n) return 1;
	return 0;
}

//모래를 움직인다
void moveSand(int x, int y, int dir) {
	int tx = 1, ty = 1;

	//대칭 처리
	if (dir == 2) {
		dir -= 2; ty = -1;
	}
	else if (dir == 3) {
		dir -= 2; tx = -1;
	}

	int sum = 0;
	for (int i = 0; i < R; i++)
	{
		int nx = x + (rx[dir][i] * tx);
		int ny = y + (ry[dir][i] * ty);

		//흩날린 모래 
		int now_sand = (arr[x][y] * r[dir][i]) / 100;
		sum += now_sand;

		//α가 적혀있는 칸 처리
		if (i == R-1) now_sand = arr[x][y] - sum;

		//밖으로 나간 모래 더해줌
		if (outrange(nx, ny)) ans += now_sand;
        //그 외 남게된 모래
		else arr[nx][ny] += now_sand;
	}
	arr[x][y] = 0;
}

void func(int x, int y) {

	//토네이도의 길이
	for (int step = 1; step <= n; step++)
	{
    	//토네이도는 2번씩 같은 길이로 움직인다
		for (int tc = 0; tc < 2; tc++)
		{
			for (int i = 0; i < step; i++)
			{
            	//먼저 움직여주고(y라고 적혀있는 칸으로 이동)
				x += dx[dir]; y += dy[dir];
				if (outrange(x, y)) return;
                //y라고 적혀있는 칸에서 moveSand를 호출한다.
				moveSand(x, y, dir);
			}
			dir++;
			if (dir == 4) dir = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];

	func(n/2, n/2);
	cout << ans;
}

 

/* 얻어갈 점 */

1. 좌우는 Y축 대칭, 상하는 X축 대칭 임을 이용하면, 코드를 깔끔하게 작성할 수 있다. (다만 -1을 잘 곱해줘야 한다.)

2. (a*b)/100 과 a/100 * b는 다르다.  나누기 연산이 있다면 무조건 문제에서 주어진대로 하자.

 

 

 

---