백준 20057 - 마법사 상어와 토네이도(C++)

문제 링크입니다. https://www.acmicpc.net/problem/20057

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

삼성 SW 역량 테스트 기출문제였습니다.

생각보다 귀찮은 구현 문제였습니다. 모래가 4방향으로 뿜어지는 것을 구현하는게 포인트였습니다.

문제 조건

출력 예시

토네이도가 어떻게 움직이냐에 따라서 모래의 움직임이 달라집니다. 4방향으로 움직임으로 저는 모두 만들었습니다.

 

1. 소용돌이 구현하기

void tornado() {
	int move = 1;
	int cnt = 1;
	pair<int, int> start = { N / 2 + 1, N / 2 + 1 };
	while (1) {
		if (start.first == 1 && start.second == 1) break;
		if (move % 2 == 1) {
			for (int i = 1; i <= move; i++) {
				if (start.first == 1 && start.second == 1) break;
				start.second--;
				move_sand(start.first, start.second, 0);
			}
			for (int i = 1; i <= move; i++) {
				if (start.first == 1 && start.second == 1) break;
				start.first++;
				move_sand(start.first, start.second, 3);
			}
		}
		else {
			for (int i = 1; i <= move; i++) {
				if (start.first == 1 && start.second == 1) break;
				start.second++;
				move_sand(start.first, start.second, 1);
			}
			for (int i = 1; i <= move; i++) {
				if (start.first == 1 && start.second == 1) break;
				start.first--;
				move_sand(start.first, start.second, 2);
			}
		}
		move++;
	}
}

토네이도가 움직이는 방향을 살펴보면 Y -> X 순으로 움직입니다 (열 -> 행)

1번 움직일 때는 Y는 감소하고 X는 증가합니다.

2번 움직일 때는 Y는 증가하고 X는 감소합니다.

3, 4...번 모두 같은 규칙으로 움직입니다.

따라서 홀수번 움직일 때는 Y 감소, X 증가   /   짝수번 움직일 때는 Y 증가, X 감소 가 됩니다. 

 

(N/2 + 1, N/2 + 1)위치에서 움직여서 (1,1) 에서 끝납니다. 따라서 (1,1)에 도착했을 경우, while을 빠져나올수 있도록 했습니다.

 

코드를 보면 (Y 감소 -> 0), (Y 증가 -> 1), (X 감소 -> 2), (X 증가 -> 3)으로 만든 것을 볼 수 있습니다.

이는 상하좌우 모래가 퍼지는 방향을 정한 것입니다.

 

 

2. 4방향으로 모래 퍼지는 것 구현하기

상하좌우로 움직일때

int dx[4][10] = {
					{ -2,-1,-1,-1,2,1,1,1,0,0 },
					{ -2,-1,-1,-1,2,1,1,1,0,0 },
					{ 0,-1,0,1,0,-1,0,1,-2,-1 },
					{ 0,-1,0,1,0,-1,0,1,2,1 }
				};
int dy[4][10] = { 
					{ 0,-1,0,1,0,-1,0,1,-2,-1 },
					{ 0,-1,0,1,0,-1,0,1,2,1 },
					{ 2,1,1,1,-2,-1,-1,-1,0,0 },
					{ 2,1,1,1,-2,-1,-1,-1,0,0 }
				};
int per[4][9] = {
					{ 2,10,7,1,2,10,7,1,5 },
					{ 2,1,7,10,2,1,7,10,5 },
					{ 2,10,7,1,2,10,7,1,5 },
					{ 2,1,7,10,2,1,7,10,5 }
				};

각각 좌우상하 방향으로 모래가 퍼지는 것을 만든 것입니다.

하나의 기준을 정한뒤, 돌려가면서 만들면 쉽게 구현할 수 있습니다.

 

 

문제 접근 방법

1. 토네이도가 움직이기 전, 모래수 구하기

2. 방향에 따라 모래 퍼뜨리기

   2-1. 퍼지는 곳이 범위 안일 경우,  map에 더해주기

   2-2. 퍼지는 곳이 범위 밖일 경우, 모래 수에서만 빼주기

3. 모래가 전부 퍼지고 난뒤, 모래수 구하기

4. First - Last 값을 구하기

 

 

자세한 것은 코드를 참고해주세요.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int N;
long long int map[501][501];
long long int first, last;

int dx[4][10] = {
					{ -2,-1,-1,-1,2,1,1,1,0,0 },
					{ -2,-1,-1,-1,2,1,1,1,0,0 },
					{ 0,-1,0,1,0,-1,0,1,-2,-1 },
					{ 0,-1,0,1,0,-1,0,1,2,1 }
				};
int dy[4][10] = { 
					{ 0,-1,0,1,0,-1,0,1,-2,-1 },
					{ 0,-1,0,1,0,-1,0,1,2,1 },
					{ 2,1,1,1,-2,-1,-1,-1,0,0 },
					{ 2,1,1,1,-2,-1,-1,-1,0,0 }
				};
int per[4][9] = {
					{ 2,10,7,1,2,10,7,1,5 },
					{ 2,1,7,10,2,1,7,10,5 },
					{ 2,10,7,1,2,10,7,1,5 },
					{ 2,1,7,10,2,1,7,10,5 }
				};

void check_first() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] > 0) first += map[i][j];
		}
	}
}

void check_last() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] > 0) last += map[i][j];
		}
	}
}

void move_sand(int x, int y, int way) {
	long long int remain = map[x][y];
	for (int i = 0; i < 9; i++) {
		int xx = x + dx[way][i];
		int yy = y + dy[way][i];
		if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
			long long int sand = map[x][y] * per[way][i] / 100;
			remain -= sand;
			map[xx][yy] += sand;
		}
		else {
			long long int sand = map[x][y] * per[way][i] / 100;
			remain -= sand;
		}
	}
	map[x][y] = 0;
	map[x + dx[way][9]][y + dy[way][9]] += remain;
}

void tornado() {
	int move = 1;
	int cnt = 1;
	pair<int, int> start = { N / 2 + 1, N / 2 + 1 };
	while (1) {
		if (start.first == 1 && start.second == 1) break;
		if (move % 2 == 1) {
			for (int i = 1; i <= move; i++) {
				if (start.first == 1 && start.second == 1) break;
				start.second--;
				move_sand(start.first, start.second, 0);
			}
			for (int i = 1; i <= move; i++) {
				if (start.first == 1 && start.second == 1) break;
				start.first++;
				move_sand(start.first, start.second, 3);
			}
		}
		else {
			for (int i = 1; i <= move; i++) {
				if (start.first == 1 && start.second == 1) break;
				start.second++;
				move_sand(start.first, start.second, 1);
			}
			for (int i = 1; i <= move; i++) {
				if (start.first == 1 && start.second == 1) break;
				start.first--;
				move_sand(start.first, start.second, 2);
			}
		}
		move++;
	}
}

void solve() {
	check_first();
	tornado();
	check_last();
	//cout << first << "   " << last << "\n";
	cout << first - last;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!