boj, 백준) 20056. 마법사 상어와 파이어볼 (C / C++)

1. 문제 링크

www.acmicpc.net/problem/20056

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

2. 문제 개요

마법사 상어가 크기가 N x N인 격자에 파이어볼 M개를 발사한다. 가장 처음 파이어볼은 각자 위치에서 이동을 대기하고있다... 등등 문제가 길고 복잡해서 문제는 다 안다고 가정하겠습니다.

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

 

3. 문제 힌트

(1) 파이어볼을 어떻게 가지고 있을 것인지 생각해보자. (어떠한 자료구조)

 

(2) 파이어볼이 겹쳐있다는 걸 어떻게 알아내고 어떻게 합칠 것인지 생각해보자.((1)과의 관계)

 

(3) 그외.. 문제를 잘 읽어보자..

 

 

4. 문제 풀이

그냥 문제가 제시하는 내용을 얼마나 코드로 잘 옮길 수 있느냐가 관건인 문제이다. 문제를 제출하고 다른 사람의 메모리 사용량, 시간 등을 보니 메모리가 5배 정도 차이나는 풀이도 있고.. 여튼 질량이 0인 파이어볼도 지워주지 않고 아마 계속 들고 있는 풀이인 것 같았다. 이 풀이도 통과 하는 거 보면 그냥 생각나는 대로 바로 코드로 옮겨도 괜찮을 것 같았다.

 

다른 이야기는 그만하고,

 

여기서 중요한 부분은

(1) 파이어볼을 갖고 있는 벡터,

   - 수량이 달라지기 때문에 벡터 사용.

 

(2) 맵. (벡터로 표현. 합치기 위함)

   - 중복된 파이어볼을 합칠 때 O(1)시간에 (1)번 자료구조(합쳐질 파이어볼들)에 접근하지 못하면 불필요한 시간을 사용할 거라 생각하고 2차원 벡터로 선언.

 

(3) 이동

   - 나머지 연산을 사용하기 위해 맵이 1~N이었던 것을 0~N-1로 표현. (맵이 붙어있음. 원형으로)

 

이 정도만 종이에 써가면서 생각했었고 나머지는 문제에 적힌 것 그대로 코드로 옮겼다.

 

 

파이어볼을 하나의 맵에 놓고 이동할 때 예외가 하나 있는데,

맵을 위에서 밑으로, 왼쪽에서 오른쪽으로 훑을 때, 예를 들어 (0,0)에 있던 파이어볼이 (0,3)으로 이동했고 하자. 그런데 (0,1), (0,2) 탐색하고 (0,3)에 왔을 때 또 이동할 수 있는 그런 문제가 발생할 수 있다. 그래서 이동 따로, 맵에 표현 따로 2개의 변수가 필요한 것을 알 수 있다.

 

홀수, 짝수 표현하는 것도 단순히 bool 연산을 사용해서 했고 코드를 보시는편이 이해가 잘 될 것 같습니다!

 

 

5. 코드

#include <cstdio>
#include <vector>
using namespace std;

struct FIREBALL {
	FIREBALL() {}
	FIREBALL(int y_, int x_, int m_, int s_, int d_) :y(y_), x(x_), m(m_), s(s_), d(d_) {}
	int y, x, m, s, d;
};

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

int n, m, k, ans;
vector<FIREBALL> map[50][50];	//0~49
vector<FIREBALL> v;	

int main()
{
	scanf("%d %d %d", &n, &m, &k);

	for (int i = 0; i < m; ++i) {
		int y, x, m, s, d;
		scanf("%d %d %d %d %d", &y, &x, &m, &s, &d);
		v.push_back(FIREBALL(y - 1, x - 1, m, s, d));	//0 ~ N-1
	}

	while (k--)
	{
		//move
		for (int i = 0; i < v.size(); ++i) {

			int nx = (v[i].x + dx[v[i].d] * v[i].s) % n;
			int ny = (v[i].y + dy[v[i].d] * v[i].s) % n;

			if (nx < 0) {
				nx += n;
			}
			if (ny < 0) {
				ny += n;
			}

			v[i].x = nx;
			v[i].y = ny;
		}

		//map init
		for (int i = 0; i < n; ++i) 
			for (int j = 0; j < n; ++j)
				map[i][j].clear();
		
		//project to map
		for (int i = 0; i < v.size(); ++i)
			map[v[i].y][v[i].x].push_back(v[i]);
		
		//vector init for next moving
		v.clear();

		//aggregate
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {

				if (map[i][j].size() == 1) {
					v.push_back(map[i][j][0]);
				}
				else if (map[i][j].size() >= 2) {
					int m_sum = 0, s_sum = 0;
					bool is_even = true, is_odd = true;

					for (FIREBALL fireball : map[i][j])
					{
						m_sum += fireball.m;
						s_sum += fireball.s;

						if (fireball.d % 2 == 0) {
							is_odd = false;
						}
						else{
							is_even = false;
						}
					}

					int m_next = m_sum / 5;
					int s_next = s_sum / map[i][j].size();

					if (m_next == 0)
						continue;

					if (is_even || is_odd) {
						v.push_back(FIREBALL(i, j, m_next, s_next, 0));
						v.push_back(FIREBALL(i, j, m_next, s_next, 2));
						v.push_back(FIREBALL(i, j, m_next, s_next, 4));
						v.push_back(FIREBALL(i, j, m_next, s_next, 6));
					}
					else
					{
						v.push_back(FIREBALL(i, j, m_next, s_next, 1));
						v.push_back(FIREBALL(i, j, m_next, s_next, 3));
						v.push_back(FIREBALL(i, j, m_next, s_next, 5));
						v.push_back(FIREBALL(i, j, m_next, s_next, 7));
					}
				}
			}
		}
	}

	for (FIREBALL item : v)
		ans += item.m;

	printf("%d", ans);

	return 0;
}

6. 결과