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

문제 링크

---

www.acmicpc.net/problem/20056

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

 

접근 방법

---

문제에 제시된 대로 구현을 하면 됩니다.

큰 범주로 나누어 본다면

 

1. 파이어볼이 자신의 정보를 가지고 이동

2. 격자 정보에 따라 파이어볼을 합치고 분해하여 파이어볼의 정보 갱신

 

1. 파이어볼의 이동은 2가지 동작으로 구분 지었습니다.

 

1-1. 파이어볼을 이동시키기 전 격자를 스캔하며 파이어볼의 정보를 vector<fire> fires에 저장함과 동시에 격자에서 제거를 합니다.

 제거를 하는 이유는 fires의 정보를 가지고 파이어볼들을 재배치를 하기 위함입니다. 또한 미리 fires에 정보를 저장하는 이유는 격자에서 바로바로 옮기게 되면 현재 보고 있는 불이 이동을 했는지 아닌지에 대한 검사를 하는 과정이 더 요구 될 것이기 때문입니다.

void moveAll() {

	vector<fire> fires;

	for (int i = 0; i < N; i++)  //격자에서 불을 제거하며 정보를 벡터에 담는다.
		for (int j = 0; j < N; j++) 
			while(!map[i][j].empty()){
				fire elem = map[i][j].back();
				map[i][j].pop_back();
				fires.push_back(elem);
			}

	for (int i = 0; i < fires.size(); i++)
		moveOne(fires[i]);
}

 

1-2. 이제 1-1에서 fires에 저장한 정보를 바탕으로 파이어볼을 하나씩 이동시킬 것입니다. 

 이동 시킬 때의 조건으로는 격자에서 파이어볼이 순회하는 구조이므로 좌표가 N - 1을 벗어난다면 0으로, 0을 벗어난다면  N - 1로 이동시켜 주어야 합니다. 

 또한 파이어볼을 방향으로 속도의 횟수 만큼 한 칸씩 이동시켜도 시간초과에는 걸리지 않으나 한 파이어볼에 대해 최대 1000번의 반복문이 연산이 될 수 있으므로 주기를 검사해 반복되는 연산을 최소화 시켜주어야 합니다.

 

만약 4X4격자에서 S지점에서 오른쪽으로 11칸을 진행한다고 하면 아래 그림과 같습니다.

여기서 주기는 4가 될 것이며 주기만큼 이동하면 자신의 원래 위치로 오게 될 것 입니다. 즉 4, 8일 때 출발위치와 같아질 것입니다. 그렇다면 남은거리는 leftDistance = (totalDistance) % N 이 될 것이며 남은 거리만큼 범위를 신경써서 이동시키면 됩니다.

void moveOne(fire elem) {

	int next_x = elem.x + direction[elem.d].first * elem.s;
	int next_y = elem.y + direction[elem.d].second * elem.s;

	if (!inRange(next_x, next_y)) {
		
		next_x = elem.x;
		next_y = elem.y;
		int leftDist = elem.s % N;

		while (--leftDist >= 0) {
			next_x += direction[elem.d].first;
			next_y += direction[elem.d].second;
			next_x = (next_x > N - 1) ? 0 : next_x;
			next_x = (next_x < 0) ? N - 1 : next_x;
			next_y = (next_y > N - 1) ? 0 : next_y;
			next_y = (next_y < 0) ? N - 1 : next_y;
		}
	}
	map[next_x][next_y].push_back({ next_x, next_y, elem.m, elem.s, elem.d });
}

 

 

2. 파이어볼의 이동 이후 격자를 스캔하며 2개 이상의 파이어볼이 있는 곳에 대해 합과 분해를 합니다.

void processing() { //합과 분해

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			if (map[i][j].size() > 1) {
				fire fireball = composition(map[i][j]); //합쳐진 파이어볼의 정보
				decomposition(fireball);
			}
}

 

2-1. 합의 과정에 있어서 방향을 설정하는 것은 아래와 같은 코드로 구현을 하였습니다.

if (tmp == ball.d % 2)
	dir *= 1;
else
	dir *= 0;

 tmp는 이전 방향의 정보이며 현재 방향과 일치하는지 비교를 합니다. dir은 1로 초기화 되어있으며 한 번이라도 방향이 이전과 달라진다면 dir은 0이 될 것이며 이 후에는 어떤 수를 dir에 곱해주어도 dir은 0을 유지합니다.

 

소스 코드

---

#include <iostream>
#include <vector>

using namespace std;

typedef struct fire {
	int x, y, m, s, d;
};

pair <int, int> direction[8] = { {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1} };
vector<fire> map[52][52];
int N, M, K;

bool inRange(int x, int y) {
	return (0 <= x && x < N && 0 <= y && y < N);
}

int messSum() {

	int sum = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			vector<fire> area = map[i][j];
			for (fire &one : area) 
				sum += one.m;
		}
	}
	return sum;
}

void decomposition(fire &fireball) { //분해

	//방향 처리를 위한 숫자 전환
	//모든 방향이 홀이거나 짝수이면 dir은 0 아니라면 1
	int d = (fireball.d == 0) ? 1 : 0; 

	for (int i = 0; i < 4; i++) 
		if(fireball.m > 0)
			map[fireball.x][fireball.y].push_back({ fireball.x, fireball.y, fireball.m, fireball.s, d + (i * 2) });
}

fire composition(vector<fire> &area) { //합

	int dir = 1;
	int cnt = area.size();
	int mSum = 0 , sSum = 0;
	int tmp = area.back().d % 2;
	int x = area.back().x;
	int y = area.back().y;
	
	while (!area.empty()) {
		
		fire ball = area.back();
		area.pop_back();

		mSum += ball.m;
		sSum += ball.s;

		if (tmp == ball.d % 2)
			dir *= 1;
		else
			dir *= 0;
		tmp = ball.d % 2;
	}
	//모든 방향이 홀이거나 짝수이면 dir은 1 반환, 아니라면 0반환
	return { x, y, mSum / 5, sSum / cnt, dir };
}

void processing() { //합과 분해

	for (int i = 0; i < N; i++) 
		for (int j = 0; j < N; j++) 
			if (map[i][j].size() > 1) {
				fire fireball = composition(map[i][j]); //합쳐진 파이어볼의 정보
				decomposition(fireball);
			}
}

void moveOne(fire elem) {

	int next_x = elem.x + direction[elem.d].first * elem.s;
	int next_y = elem.y + direction[elem.d].second * elem.s;

	if (!inRange(next_x, next_y)) {
		
		next_x = elem.x;
		next_y = elem.y;
		int leftDist = elem.s % N;

		while (--leftDist >= 0) {
			next_x += direction[elem.d].first;
			next_y += direction[elem.d].second;
			next_x = (next_x > N - 1) ? 0 : next_x;
			next_x = (next_x < 0) ? N - 1 : next_x;
			next_y = (next_y > N - 1) ? 0 : next_y;
			next_y = (next_y < 0) ? N - 1 : next_y;
		}
	}
	map[next_x][next_y].push_back({ next_x, next_y, elem.m, elem.s, elem.d });
}

void moveAll() {

	vector<fire> fires;

	for (int i = 0; i < N; i++)  //맵에서 불을 제거하며 정보를 벡터에 담는다.
		for (int j = 0; j < N; j++) 
			while(!map[i][j].empty()){
				fire elem = map[i][j].back();
				map[i][j].pop_back();
				fires.push_back(elem);
			}

	for (int i = 0; i < fires.size(); i++)
		moveOne(fires[i]);
}

int solve() {

	while (--K >= 0) {
		moveAll();
		processing();
	}
	return messSum();
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> K;

	for (int i = 0; i < M; i++) {
		int r, c, m, s, d;
		cin >> r >> c >> m >> s >> d;
		map[r - 1][c - 1].push_back({ r - 1,c - 1,m,s,d });
	}
	cout << solve();
}