백준 20056 - 마법사 상어와 파이어볼

문제링크

• 백준 20056

문제설명

• 크기가 NxN인 격자에 M개의 파이어볼이 있다.
• 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번 행과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
  • 순환하는 구조
• 파이어볼은 8가지 방향으로 움직일 수 있다.
  • 0: 북쪽, 1: 북동쪽, 2: 동쪽, 3: 남동쪽, 4: 남쪽, 5: 남서쪽, 6: 서쪽, 7: 북서쪽
• 모든 파이어볼은 위치(r,c), 질량(m), 방향(d), 속력(s) 를 가진다.
• 파이어볼 이동 명령은 다음과 같다.
  • 모든 파이어볼이 자신의 방향 d로 속력 s칸 만큼 이동한다.
    • 이동 과정에서 같은 칸에 여러 개의 파이어볼이 존재할 수 있다.
  • 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
    • 같은 칸에 있는 파이어볼이 모두 하나로 합쳐진 후 4개의 파이어볼로 나누어진다.
    • 나누어진 파이어볼의 질량은 (합쳐진 파이어볼 질량의 합)/5, 속력은 (합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼 개수) 이다. (소수점은 버림)
    • 합쳐지는 파이어볼의 방향이 모두 홀수이거나 짝수이면, 방향은 0,2,4,6 이 되고 그렇지 않으면 1,3,5,7 이 된다.
    • 질량이 0인 파이어볼은 소멸되어 없어진다.
• K번 이동 명령 후 남아있는 파이어볼 질량의 합을 구하라.

문제접근

• 파이어볼의 정보를 담는 구조체를 선언한다. (질량, 속도, 방향)
• 벡터 컨테이터를 활용한 인접리스트로 파이어볼 데이터를 관리한다.
  • ballTable[r][c][i] 는 (r,c)에 위치한 i번째 파이어볼을 의미한다.
• 파이어볼 좌표 이동
• 한칸씩 방향대로 이동하다가 좌표를 벗어나는 경우 연결된 격자의 끝판으로 이동할 수 있도록 한다.
• nballTable 인접리스트에 이동한 파이어볼들의 데이터를 넣어두고, 모든 파이어볼 이동이 끝나면 ballTable 을 갱신할 수 있도록 한다.
• 파이어볼 나누기
• 같은 좌표에 2개 이상 파이어볼이 있는 경우 나누어지는 질량, 속도, 방향이 결정된 nball 데이터를 만든다.
  • 질량이 0인 경우는 파이어볼이 소멸되므로 nballTable 에 아무것도 넣지 않는다.

구현

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

typedef struct _ball {
	int mass, speed, dir;
} Fireball;

int N, M, K;
// 0 ~ 7 이동 방향
int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
vector<Fireball> ballTable[51][51];

void printBall() {
	printf("--------------------\n");
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			printf("[%d, %d] Fireball (Mass, Speed, Dir): ", r, c);
			for (int i = 0; i < ballTable[r][c].size(); i++) {
				printf("(%d, %d, %d)", ballTable[r][c][i].mass, ballTable[r][c][i].speed, ballTable[r][c][i].dir);
			}
			printf("\n");
		}
	}
}

int afterMove() {
	vector<Fireball> nballTable[51][51];
	int ret = 0;

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			// 같은 칸에 파이어볼은 모두 하나로 합쳐진다.
			int sumMass = 0, sumSpeed = 0, count = 0;
			bool odd = true, even = true;
			for (int i = 0; i < ballTable[r][c].size(); i++) {
				sumMass += ballTable[r][c][i].mass;
				sumSpeed += ballTable[r][c][i].speed;
				count++;
				if (ballTable[r][c][i].dir % 2 == 0) odd = false;
				else even = false;
			}
			if (count >= 2) {
				int nmass = sumMass / 5;
				int nspeed = sumSpeed / count;
				Fireball nball[4];
				if (nmass == 0) { // 질량이 0인 파이어볼은 소멸
					ballTable[r][c].clear();
					continue;
				}
				if (odd || even) { // 방향이 모두 홀수 혹은 짝수인 경우
					nball[0] = { nmass, nspeed, 0 };
					nball[1] = { nmass, nspeed, 2 };
					nball[2] = { nmass, nspeed, 4 };
					nball[3] = { nmass, nspeed, 6 };
				}
				else {
					nball[0] = { nmass, nspeed, 1 };
					nball[1] = { nmass, nspeed, 3 };
					nball[2] = { nmass, nspeed, 5 };
					nball[3] = { nmass, nspeed, 7 };
				}
				for (int k = 0; k < 4; k++)
					nballTable[r][c].push_back(nball[k]);
			}
			else if(count==1) {
				nballTable[r][c].push_back(ballTable[r][c][0]);
			}
			ballTable[r][c].clear();
		}
	}

	// update ballTable
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			for (auto ele : nballTable[r][c]) {
				ret += ele.mass;
				ballTable[r][c].push_back(ele);
			}
		}
	}

	return ret;
}

void moveFireball() {
	vector<Fireball> nballTable[51][51];

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			for (int i = 0; i < ballTable[r][c].size(); i++) {
				int nextX = r;
				int nextY = c;
				Fireball ball = ballTable[r][c][i];
				for (int s = 0; s < ball.speed; s++) {
					nextX += dx[ball.dir];
					nextY += dy[ball.dir];
					if (nextX < 1) nextX = N;
					else if (nextX > N) nextX = 1;
					if (nextY < 1) nextY = N;
					else if (nextY > N) nextY = 1;
				}
				nballTable[nextX][nextY].push_back(ball);
			}
			ballTable[r][c].clear();
		}
	}

	// update ballTable
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			for (auto ele : nballTable[r][c]) {
				ballTable[r][c].push_back(ele);
			}
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	scanf("%d %d %d", &N, &M, &K);
	int x, y, m, s, d;
	Fireball ball;

	for (int i = 0; i < M; i++) {
		scanf("%d %d %d %d %d", &x, &y, &m, &s, &d);
		ball = { m,s,d };
		ballTable[x][y].push_back(ball);
	}

	int ans = 0;
	for (int i = 0; i < K; i++) {
		moveFireball();
		// printBall();
		ans = afterMove();
		if (ans == 0) break;
	}
	printf("%d\n", ans);
	return 0;
}