[삼성역량테스트] 20057 마법사 상어와 토네이도

 

풀이일시 : 2021-01-10

 

문제 : 

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 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

 

풀이 : 

2020년도 하반기 삼성 역량테스트 문제이다.

 

고려할 것은 두가지로 그림에 나타나 있다.

 

1. 

가운데에서 시작하여 

 

1칸이동 - 좌 - 하

2칸이동 - 우 - 상

3칸이동 - 좌 - 하

4칸이동 - 우 - 상

...

을 반복한다. 

 

2. 

또한 움직일때마다 모래는 흩날리게 된다.

 

여기서 주의할 사항은 비율대로 움직이나 소수점 아래는 버린 정수만큼 이동하고

 

y에 있던 값에서 움직인 값을 뺀 값이 a 값이 되는 것이다.

 

계속해서 a값을 55%로 두고 풀어서 실패했다. 이부분을 이해하고 넘어가길 바란다.

 

---

첫번째 고려사항은 결국 숫자가 증가하는 것은 '하' 이동 후와 '상' 이동 후 이기 때문에 하or상의 동작을 하게되면 cnt를 +1 해주고 그 cnt만큼 for loop를 돌아 모래를 이동시켜 줄 수 있었다.

 

두번째 고려사항은 우선 나는 모래를 아무리 끝자락에서 민다고 해도 밖으로 나가는 모래는 최대 두칸까지밖에 나가지 않는다는 점을 고려했다.

 

이를 통해 만약 5x5 크기의 배열이 주어진다면 9x9 배열을 선언해준다면 상하좌우 2칸씩 나간 모래의 양도 한 배열에 나타낼 수 있을 것이다.

 

 

그리고 나간 모래들을 구할 때에는 전체 배열의 수를 더해준 뒤 가운데의 5x5 배열의 합을 빼주면 될 것이다.

 

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

#include <iostream>

using namespace std;

int N;
int map[504][504];
int temp;
int dir, r, c;
int cnt = 0;
int go;

void move(int dir,int r,int c) { 

	if ((dir == 1)&& (c>2)) { //좌로이동
		cnt++;
		for (int i = 0; i < cnt; i++) {
			if (r == 2 && c == 2) //끝에 다다르면 return 한다. 0,1은 빈 스페이스로 나둠
				return;
			int y = map[r][c - 1];
			float re = y / 100.0;
			int a = y - int(re * 5) - int(re * 1) - int(re * 7) - int(re * 10) - int(re * 2) - int(re * 1) - int(re * 7) -int( re * 10) - int(re * 2);
            
			map[r][c - 1] = 0;
			map[r][c - 2] += a; //a 는 55%가 아니다.. 남은 모래 전부 다이다..!!!!!!
			map[r][c - 3] += int(re * 5);
			map[r - 1][c] += int(re * 1);
			map[r - 1][c - 1] += int(re * 7);
			map[r - 1][c - 2] += int(re * 10);
			map[r - 2][c - 1] += int(re * 2);
			map[r + 1][c] += int(re * 1);
			map[r + 1][c - 1] += int(re * 7);
			map[r + 1][c - 2] += int(re * 10);
			map[r + 2][c - 1] += int(re * 2);
			c--;//한번 진행했으니 c가 줄어들것
		}
		dir = 2;
		move(dir, r, c);
	}

	else if ((dir == 2) && (r < N + 2)) { //하로이동
		for (int i = 0; i < cnt; i++) {
			int y = map[r + 1][c]; //y지점은 0이되고 이 지점에있는
			float re = y / 100.0;
			int a = y - int(re * 5) - int(re * 1) - int(re * 7) - int(re * 10) - int(re * 2) - int(re * 1) - int(re * 7) - int(re * 10) - int(re * 2);

			map[r + 1][c] = 0;
			map[r + 2][c] += a;
			map[r + 3][c] += re * 5;
			map[r][c - 1] += re * 1;
			map[r + 1][c - 1] += re * 7;
			map[r + 2][c - 1] += re * 10;
			map[r + 1][c - 2] += re * 2;
			map[r][c + 1] += re * 1;
			map[r + 1][c + 1] += re * 7;
			map[r + 2][c + 1] += re * 10;
			map[r + 1][c + 2] += re * 2;
			r++;
		}
		dir = 3;
		move(dir, r, c);
	}
	else if ((dir == 3) && (c < N+2)) { //우로이동
		cnt++;
		for (int i = 0; i < cnt; i++) {
			int y = map[r][c + 1];
			float re = y / 100.0;
			int a = y - int(re * 5) - int(re * 1) - int(re * 7) - int(re * 10) - int(re * 2) - int(re * 1) - int(re * 7) - int(re * 10) - int(re * 2);
			map[r][c + 1] = 0;
			map[r][c + 2] += a;
			map[r][c + 3] += re * 5;
			map[r - 1][c] += re * 1;
			map[r - 1][c + 1] += re * 7;
			map[r - 1][c + 2] += re * 10;
			map[r - 2][c + 1] += re * 2;
			map[r + 1][c] += re * 1;
			map[r + 1][c + 1] += re * 7;
			map[r + 1][c + 2] += re * 10;
			map[r + 2][c + 1] += re * 2;
			c++;//한번 진행했으니 c가 줄어들것
		}
		dir = 4;
		move(dir, r, c);
	}
	else if ((dir == 4) && (r > 2)) { //상으로이동
		for (int i = 0; i < cnt; i++) {
			int y = map[r - 1][c]; //y지점은 0이되고 이 지점에있는
			float re = y / 100.0;
			int a = y - int(re * 5) - int(re * 1) - int(re * 7) - int(re * 10) - int(re * 2) - int(re * 1) - int(re * 7) - int(re * 10) - int(re * 2);

			map[r - 1][c] = 0;
			map[r - 2][c] += a;
			map[r - 3][c] += re * 5;
			map[r][c - 1] += re * 1;
			map[r - 1][c - 1] += re * 7;
			map[r - 2][c - 1] += re * 10;
			map[r - 1][c - 2] += re * 2;
			map[r][c + 1] += re * 1;
			map[r - 1][c + 1] += re * 7;
			map[r - 2][c + 1] += re * 10;
			map[r - 1][c + 2] += re * 2;
			r--;
		}
		dir = 1;
		move(dir, r, c);
	}
}
int sum_move() {
	int sum1 = 0;
	int sum2 = 0;
	for (int i = 0; i < N+4; i++) {
		for (int j = 0; j < N+4; j++) {
			sum1 += map[i][j];
		}
	}
	for (int i = 2; i < N+2 ; i++) {
		for (int j = 2; j < N+2; j++) {
			sum2 += map[i][j];
		}
	}
	return sum1 - sum2;
}

int main() {
	cin >> N;
	for (int i = 2; i < N+2; i++) {
		for (int j = 2; j < N+2; j++) {
			cin >> map[i][j];
		}
	}

	dir = 1; //시작방향 '좌'
	r = ((N + 2) / 2) + 1;
	c = ((N + 2) / 2) + 1; //중앙 점
	move(dir, r, c);
	int result = sum_move();
	printf("%d", result);

	return 0;
}

 

개인적으로 코드가 많이 지저분하다고 생각된다. %를 곱해주는 것은 반복된 작업이고 이동 또한 반복된 일이기 때문에 이를 한번에 묶어 표현하면 코드가 깔끔해 질것이라고 생각한다.

 

아래 블로그에서 잘 표현해 놓았다고 생각하여 링크를 첨부한다. 누구나 다르게 알고리즘 문제에 접근할 수 있지만 보기좋은 코드는 있는법..

 

더 발전해야겠다.

 

yjyoon-dev.github.io/boj/2020/11/07/boj-20057/?

[BOJ][삼성기출] 백준 20057번 - 마법사 상어와 토네이도 풀이