백준 20056 - 마법사 상어와 파이어볼(C++)

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

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

삼성 SW 역량테스트 기출문제입니다. 문제 조건에 따라 구현만 하면 되는 문제였습니다. 

문제 조건

출력 예시

1. 파이어볼 움직이기

typedef struct fire {
	int x;
	int y;
	int m;
	int s;
	int d;
}fire;
int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
vector<fire> fire_ball;

void move_fire_ball() {
	for (int i = 0; i < fire_ball.size(); i++) {
		if (fire_ball[i].m > 0) {
			for (int j = 0; j < fire_ball[i].s; j++) {
				fire_ball[i].x += dx[fire_ball[i].d];
				fire_ball[i].y += dy[fire_ball[i].d];
				if (fire_ball[i].x == 0) fire_ball[i].x = N;
				if (fire_ball[i].y == 0) fire_ball[i].y = N;
				if (fire_ball[i].x == N + 1) fire_ball[i].x = 1;
				if (fire_ball[i].y == N + 1) fire_ball[i].y = 1;
			}
			map[fire_ball[i].x][fire_ball[i].y]++;
			now_fire[fire_ball[i].x][fire_ball[i].y].push_back(i);
		}
	}
}

파이어볼은 5개의 정보를 가지고 있습니다. 

구조체를 사용하여 파이어볼의 정보를 저장하고, vector를 통해 파이어볼을 저장했습니다.

 

파이어볼은 D방향으로 움직임으로 dx, dy를 통해 움직임을 만들었습니다. 

이때 1번 행렬은 N번 행렬과 연결되어 있음으로 0번 행,열 혹은 N+1번 행,열에 도달했다면, 각각 N번과 1번 행,렬로 바꿔줘야합니다.

 

움직임이 끝난 뒤의 파이어볼 위치를 저장해야합니다. -> 똑같은 위치에 2개 이상이 있다면 분할해야하기 때문입니다.

 

 

2. 파이어볼 나누기

void divide_fire(int x, int y) {
	int new_M = 0;
	int new_S = 0;
	int new_D = 0; // 홀수일 경우 +1. 짝수일 경우 -1
	for (int i = 0; i < now_fire[x][y].size(); i++) {
		new_M += fire_ball[now_fire[x][y][i]].m;
		new_S += fire_ball[now_fire[x][y][i]].s;
		if (fire_ball[now_fire[x][y][i]].d % 2 == 0) new_D--;
		else new_D++;
	}
	new_M /= 5;
	new_S /= now_fire[x][y].size();
	if(new_M > 0){
		if (abs(new_D) == now_fire[x][y].size()) {
			for (int i = 0; i < 4; i++) {
				new_fire.push_back({ x,y,new_M,new_S, 0 + i * 2 });
			}
		}
		else {
			for (int i = 0; i < 4; i++) {
				new_fire.push_back({ x,y,new_M,new_S, 1 + i * 2 });
			}
		}
	}
}

(X , Y) 위치에 파이어볼의 갯수가 2개 이상이라면, 4개의 파이어볼로 분할해야합니다.

이때 새로운 질량 = (해당 좌표에서의 파이어볼들의 질량) / 5

       새로운 속력 = (해당 좌표에서의 파이어볼들의 속력) / (파이어볼의 갯수)

       새로운 방향 = 홀수 or 짝수가 몇개인가?

 

방향의 경우 전부 홀수 or 짝수라면 각각 0,2,4,6이 되고, 섞여있을 경우 1,3,5,7이 됩니다.

저는 파이어볼의 방향이 홀수일 경우 +1을 했으며, 짝수일 경우 -1를 했습니다. 

방향의 합의 절댓값이 파이어볼의 갯수와 같아질 경우, 전부 홀수 or 짝수라는 의미가 되니, 쉽게 방향을 구할 수 있습니다.

 

 

문제 접근 방법

1. 파이어볼의 정보를 저장한다.

2. 파이어볼을 움직인다.

3. (X,Y)에서 파이어볼의 갯수가 2개 이상일 경우 분할한다.

4. (1 ~ 3) 과정을 K번 반복한다.

 

 

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

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

using namespace std;

int N, M, K;
int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
int map[51][51];
typedef struct fire {
	int x;
	int y;
	int m;
	int s;
	int d;
}fire;
vector<fire> fire_ball;
vector<fire> new_fire;
vector<int> now_fire[51][51];

void move_fire_ball() {
	for (int i = 0; i < fire_ball.size(); i++) {
		if (fire_ball[i].m > 0) {
			for (int j = 0; j < fire_ball[i].s; j++) {
				fire_ball[i].x += dx[fire_ball[i].d];
				fire_ball[i].y += dy[fire_ball[i].d];
				if (fire_ball[i].x == 0) fire_ball[i].x = N;
				if (fire_ball[i].y == 0) fire_ball[i].y = N;
				if (fire_ball[i].x == N + 1) fire_ball[i].x = 1;
				if (fire_ball[i].y == N + 1) fire_ball[i].y = 1;
			}
			map[fire_ball[i].x][fire_ball[i].y]++;
			now_fire[fire_ball[i].x][fire_ball[i].y].push_back(i);
		}
	}
}

void divide_fire(int x, int y) {
	int new_M = 0;
	int new_S = 0;
	int new_D = 0; // 홀수일 경우 +1. 짝수일 경우 -1
	for (int i = 0; i < now_fire[x][y].size(); i++) {
		new_M += fire_ball[now_fire[x][y][i]].m;
		new_S += fire_ball[now_fire[x][y][i]].s;
		if (fire_ball[now_fire[x][y][i]].d % 2 == 0) new_D--;
		else new_D++;
	}
	new_M /= 5;
	new_S /= now_fire[x][y].size();
	if(new_M > 0){
		if (abs(new_D) == now_fire[x][y].size()) {
			for (int i = 0; i < 4; i++) {
				new_fire.push_back({ x,y,new_M,new_S, 0 + i * 2 });
			}
		}
		else {
			for (int i = 0; i < 4; i++) {
				new_fire.push_back({ x,y,new_M,new_S, 1 + i * 2 });
			}
		}
	}
}

void check_fire() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (now_fire[i][j].size() >= 2) {
				divide_fire(i, j);
			}
			else if(now_fire[i][j].size() == 1){
				new_fire.push_back(fire_ball[now_fire[i][j][0]]);
			}
		}
	}
}

void solve() {
	int ans = 0;
	for (int i = 0; i < K; i++) {
		move_fire_ball();
		check_fire();
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				now_fire[i][j].clear();
			}
		}
		fire_ball.clear();
		fire_ball = new_fire;
		new_fire.clear();
	}
	for (int i = 0; i < fire_ball.size(); i++) {
		ans += fire_ball[i].m;
	}
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		fire x;
		cin >> x.x >> x.y >> x.m >> x.s >> x.d;
		fire_ball.push_back(x);
	}
	solve();
	return 0;
}

 

 

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