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

https://www.acmicpc.net/problem/20056

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

문제

어른 상어가 마법사가 되었고, 파이어볼을 배웠다.

마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다.

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

7	0	1
6		2
5	4	3

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
   • 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   2. 파이어볼은 4개의 파이어볼로 나누어진다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
   4. 질량이 0인 파이어볼은 소멸되어 없어진다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

입력

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

출력

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.

 

https://yabmoons.tistory.com/600

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

제 힘으로 푼 문제는 아니지만, 꼭 기억해야할 부분들이 있어 기록합니다. 이 문제에 대한 내용은 위 블로그에 들어가서 보시면 더욱 더 도움이 될 수 있는 설명이 있으니 참고바랍니다.

 

이 문제를 처음 보고, vector를 사용해야하는 건 알겠고, 구조체를 사용해야하는 것도 알았다.

하지만 아직 C++의 STL을 완벽이해하지 못했고, C 문법에 대한 이해가 더욱 잘 되어있는 상태였기 때문에 

처음에 C로 구조체를 만들고 그거에 대한 함수들을 만들면서 해결하려했다. 하지만 너무 코드가 지저분해지고 나도 내 코드가 헷갈려지면서 결국엔 3시간 동안 못풀고 다른 분의 코드를 참고하기로 했다. 그래서 참고한 내용이 위에 블로그이다.

 

구조체를 만든 후 vector에 type형태를 구조체로 선언해줌으로써 내가 만든 구조체 형태를 이루는 vector를 사용하는 방법을 배웠다.

struct infor{
	int x;
    int y;
    int m;
    int s;
    int d;
};

vector<infor> FireBall;

이런식으로 말이다. C++은 정말 배우면 배울수록 흥미롭네..

 

이 문제에서 각 좌표에서 이동하는 함수는 어찌저찌 C로 풀 때 비슷하게 풀었는데,

2개 이상 있을 때 합치고 다시 초기화 하는 함수 또한 기억해야할 것이 있었다.

 

내가 선언해서 저장했던 vector에서 크기가 2이상인 것들은 하나로 뭉친 후 4개로 나눠 초기화해주는 함수를 쓰려면 엄청 복잡해진다. 안에 있던 정보들을 빼서, 합치고, 다시 넣어주고 ,, 이런 것들을 해결해주는 방법이 내가 생각하지 못했던 방법을 사용하셔서 편하게 처리해주는 부분을 기억해야할 것 같다.

 

함수에서 임시로 vector를 하나 선언해주고, map을 돈다.

map을 돌면서 크기가 1인 것들은? 크기가 2 이상이 아니므로 합치고 다시 저장하는 작업을 할 필요없다

그냥 임시로 저장한 vector에 넣어준다.

그러면 크기가 2 이상인 것들은? 문제에서 하라는 대로 해준다. 

질량은 질량대로 구해주고, 속력도 속력대로 구해주고, 각 방향이 모두 홀수/짝수인지도 bool 변수를 통해 알아내고,

정리한 자료들을 임시 vector에 다시 넣어주는 것이다.

 

이렇게되면 임시 vector에는 본래 맵vector에서 가지고 있던 정보에서 최신화된 정보만을 저장할 수 있다.

그리고 마지막에 임시vector를 파이어볼vector에 대입해주면 파이어볼vector에는 최신화 된 정보만을 담을 수 있는 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<vector>
#include<queue>
#include<stdio.h>
#define sz 55

using namespace std;

// i번 파이어볼의 위치는 (r,c), 질량은 m, 방향은 d, 속력은 s이다
struct FireBall {
	int x;
	int y;
	int wgt;
	int speed;
	int dir;
};

int dx[] = { -1,-1,0,1,1,1,0,-1 };
int dy[] = { 0,1,1,1,0,-1,-1,-1 };

vector<FireBall> map[sz][sz];
vector<FireBall> FIREBALL;

int N, M, K;

void Move_FireBall() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			map[i][j].clear();
		}
	}

	for (int i = 0; i < FIREBALL.size(); i++) {
		int x = FIREBALL[i].x;
		int y = FIREBALL[i].y;
		int M = FIREBALL[i].wgt;
		int S = FIREBALL[i].speed;
		int Dir = FIREBALL[i].dir;

		int Move = S % N;
		int nextX = x + dx[Dir] * Move;
		int nextY = y + dy[Dir] * Move;
		if (nextX < 1) nextX += N;
		if (nextY < 1) nextY += N;
		if (nextX > N) nextX -= N;
		if (nextY > N) nextY -= N;
		map[nextX][nextY].push_back({ nextX, nextY, M, S, Dir });
		FIREBALL[i].x = nextX;
		FIREBALL[i].y = nextY;
	}
}

void Divide_Ball() {
	vector<FireBall> temp;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j].size() == 0) continue;
			if (map[i][j].size() == 1) {
				temp.push_back(map[i][j][0]);
				continue;
			}

			int Massive = 0;
			int Speed = 0;
			int Cnt = map[i][j].size();

			bool flag = true, judge = true;
			for (int ps = 0; ps < map[i][j].size(); ps++) {
				Massive += map[i][j][ps].wgt;
				Speed += map[i][j][ps].speed;
				if (map[i][j][ps].dir % 2 == 0) flag = false;
				else judge = false;
			}

			int Mass = Massive / 5;
			int res_speed = Speed / Cnt;
			if (Mass == 0) continue;
			if (flag == true || judge == true) {
				temp.push_back({ i,j,Mass,res_speed, 0 });
				temp.push_back({ i,j,Mass,res_speed, 2 });
				temp.push_back({ i,j,Mass,res_speed, 4 });
				temp.push_back({ i,j,Mass,res_speed, 6 });
			}
			else {
				temp.push_back({ i,j,Mass,res_speed, 1 });
				temp.push_back({ i,j,Mass,res_speed, 3 });
				temp.push_back({ i,j,Mass,res_speed, 5 });
				temp.push_back({ i,j,Mass,res_speed, 7 });
			}
		}
	}
	FIREBALL = temp;
}

int main() {
	cin >> N >> M >> K;

	for (int i = 0; i < M; i++) {
		int r, c, m, s, d;
		cin >> r >> c >> m >> s >> d;
		FIREBALL.push_back({ r,c,m,s,d });
	}

	while (K--) {
		Move_FireBall();
		Divide_Ball();
	}
	int ans = 0;
	for (int i = 0; i < FIREBALL.size(); i++)
		ans += FIREBALL[i].wgt;

	cout << ans << "\n";

	return 0;
}