[C++] 백준 20056번 마법사 상어와 파이어볼

20056번: 마법사 상어와 파이어볼

삼성 SW 역량 테스트 기출 문제 에 수록된 문제.

구현 / 시뮬레이션 문제로, 문제에서 요구하는 대로 풀면 된다.

 

오랜만에 풀어보는 알고리즘 문제라서 특수한 알고리즘이 필요없는 구현 문제일 줄 알았는데

시간 복잡도를 생각 안하고 풀어서 시간 초과를 냈었다.

 

 

문제풀이

다음과 같은 순서대로 구현했다

1. 모든 파이어볼을 이동시킨다.
2. 2개 이상의 파이어볼이 있는 곳에서 합친 후 4개로 나눠준다.

1번 로직과 2번 로직을 반복만 시켜주면 된다.

 

처음 접근 방식과 틀린 이유

처음에는 2개 이상의 파이어볼이 있는 곳의 좌표를 Set 자료구조에 담아두었다가

모든 FireBall을 담는 벡터에서 해당 좌표와 일치하는 곳에서 해당 파이어볼을 옮기는 형태로 코드를 짰었다.

이렇게 하면 FireBall이 엄청나게 늘어나는 테스트 케이스에서 시간초과가 발생할 수 있게 된다.

 

코드

구현 문제의 코드는 특별히 어렵지 않으므로 코드 전문을 바로 올리겠다.

/*
* 백준 20056번 마법사 상어와 파이어볼
* https://www.acmicpc.net/problem/20056
* 구현 / 시뮬레이션
*/
#include <iostream>
#include <map>
#include <vector>

using namespace std;

class FireBall {
public:
	int mass, speed, direction;

	FireBall(int mass, int speed, int direction) {
		this->mass = mass;
		this->speed = speed;
		this->direction = direction;
	}

};

pair<int, int> directionArr[8] = {
	{-1, 0},
	{-1, 1},
	{0, 1},
	{1, 1},
	{1, 0},
	{1,-1},
	{0, -1},
	{-1, -1},
};
int widthHeight, fireBallCnt, cmdCnt;
vector<vector<vector<FireBall>>> fireBallVec(51, vector<vector<FireBall>>(51, vector<FireBall>()));
vector<pair<pair<int, int>, FireBall>> moveVector;
int result;

void moveAllFireBall() {
	moveVector.clear();
	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			for (int k = 0; k < fireBallVec[i][j].size(); k++) {
				int dirIdx = fireBallVec[i][j][k].direction;
				int r = i + (directionArr[dirIdx].first * fireBallVec[i][j][k].speed);
				int c = j + (directionArr[dirIdx].second * fireBallVec[i][j][k].speed);

				if (r > widthHeight) {
					r %= widthHeight;
				}

				if (r < 1) {
					r = (r % widthHeight) + widthHeight;
				}

				if (c > widthHeight) {
					c %= widthHeight;
				}

				if (c < 1) {
					c = (c % widthHeight) + widthHeight;
				}

				moveVector.push_back({ {r,c}, fireBallVec[i][j][k] });
				fireBallVec[i][j].erase(fireBallVec[i][j].begin() + k);
				k--;
			}
		}
	}

	for (int i = 0; i < moveVector.size(); i++) {
		int r = moveVector[i].first.first;
		int c = moveVector[i].first.second;
		fireBallVec[r][c].push_back(moveVector[i].second);
	}
}

void divideDuplicatedFireBall() {
	for (int r = 1; r <= widthHeight; r++) {
		for (int c = 1; c <= widthHeight; c++) {
			if (fireBallVec[r][c].size() > 1) {
				int massSum = 0;
				int speedSum = 0;
				int duplicatedCnt = 0;

				bool isOdd = true;
				bool isEven = true;

				for (int i = 0; i < fireBallVec[r][c].size(); i++) {
					massSum += fireBallVec[r][c][i].mass;
					speedSum += fireBallVec[r][c][i].speed;
					duplicatedCnt++;

					if (fireBallVec[r][c][i].direction % 2 == 1) {
						isEven = false;
					}
					else {
						isOdd = false;
					}

					fireBallVec[r][c].erase(fireBallVec[r][c].begin() + i);
					i--;
				}


				if ((massSum / 5) > 0) {
					if (isOdd || isEven) {
						fireBallVec[r][c].push_back(
							FireBall(massSum / 5, speedSum / duplicatedCnt, 0)
						);
						fireBallVec[r][c].push_back(
							FireBall(massSum / 5, speedSum / duplicatedCnt, 2)
						);
						fireBallVec[r][c].push_back(
							FireBall(massSum / 5, speedSum / duplicatedCnt, 4)
						);
						fireBallVec[r][c].push_back(
							FireBall(massSum / 5, speedSum / duplicatedCnt, 6)
						);
					}
					else {
						fireBallVec[r][c].push_back(
							FireBall(massSum / 5, speedSum / duplicatedCnt, 1)
						);
						fireBallVec[r][c].push_back(
							FireBall(massSum / 5, speedSum / duplicatedCnt, 3)
						);
						fireBallVec[r][c].push_back(
							FireBall(massSum / 5, speedSum / duplicatedCnt, 5)
						);
						fireBallVec[r][c].push_back(
							FireBall(massSum / 5, speedSum / duplicatedCnt, 7)
						);
					}
				}
			}
		}
	}

}

void move(int idx) {
	if (idx > cmdCnt) { return; }

	moveAllFireBall();
	divideDuplicatedFireBall();
	move(idx + 1);
}

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

	cin >> widthHeight >> fireBallCnt >> cmdCnt;

	int r, c, mass, speed, direction;
	for (int i = 1; i <= fireBallCnt; i++) {
		cin >> r >> c >> mass >> speed >> direction;
		fireBallVec[r][c].push_back(FireBall(mass, speed, direction));
	}

	move(1);

	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			for (FireBall fireBall : fireBallVec[i][j]) {
				result += fireBall.mass;
			}
		}
	}

	cout << result;

	return 0;
}

 

배운 점 & 새로 안 점

C++에서 3차원 백터를 처음 써봤다. (사실 2차원 벡터를 쓰는 법도 까먹어 버렸었다.)

vector<vector<vector<FireBall>>> fireBallVec(51, vector<vector<FireBall>>(51, vector<FireBall>()));

위처럼 3차원 벡터를 만들게 되면

[51][51] 사이즈의 벡터를 담을 수 있는 3차원 벡터를 초기화시킬 수 있다.

 

백준 20056번 마법사 상어와 파이어볼 · kimyunseok/cpp@372740e