[BOJ20056][C++] 마법사 상어와 파이어볼

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

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

 

문제

 

해결

처음 생각

: 이차원 배열 board[][]에 가장 초기 파이어볼들의 위치를 저장 -> 각 파이어볼들에 대해 이동을 수행 -> 겹치는 파이어볼들에 대해 처리

그래서 board[][]를 선언하고, i번 파이어볼의 질량, 속력, 방향을 각각 m[i], s[i], d[i]에 저장하는 식으로 질량, 속력, 방향에 대한 배열을 따로 선언한 뒤 진행했다.

 

여기서 문제가 생겼다. i번 파이어볼에 대한 질량, 속도, 방향 정보는 인덱스 i로 알 수 있는데, 맨 처음에 board[][] 배열에 초기 위치를 저장한 뒤에 다시 참조하려고 했더니 board 위에 이미 올라간 파이어볼들이 각각 몇번 파이어볼인지 알 방법이 없었다. 그리고 이렇게 모두 배열로 선언했더니, 이동을 완료하고 겹치는 파이어볼에 대한 처리를 완료했을 때 새로 생긴 파이어볼들의 정보를 어떻게 저장해야할지 방법이 떠오르지 않았다.

 

초반 변수 선언부터 고전하는 바람에 구글에 살짝 검색을 했다,,

검색을 한 결과, 가장 적절한 풀이로 생각되는 것은 위치(r,c), 질량(m), 속력(s), 방향(d)을 모두 담은 struct를 선언하는 것이었다..!.!!

사실 이전에 struct를 이용하여 문제풀이를 했던 적이 없어서 생각을 못했다,, 앞으로 꼭 기억하자! (어쩐지 이 많은 정보를 한번에 담을 방법이.. ?)

 

실눈으로 struct 활용한 것만 확인하고 그 뒤 풀이는 다시 스스로 풀어나갔다. (정말이다!)

 

파이어볼을 움직이기 전과 움직인 이후에 저장할 공간을 따로 두었다. 한 곳에서 이동이 이루어지면 무조건 혼동이 발생할 것 같았기 때문이다.

vector<Fireball>로 before, after를 선언했다.

 

초기 위치를 before에 순서대로 push_back하고, 하나씩 돌면서 이동을 수행했다. 이동은 move()라는 메소드에서 수행했다. 이동은 문제의 설명을 따라 구현하면 된다. (뒤에서 엄청난 복병으로 등장할테지만ㅠ.ㅠ)

한 가지 체크할 것은 이동한 위치가 0~N-1 범위를 벗어나면 +N 또는 -N을 하여 범위 안에 들도록 해준다.

이동을 마친 파이어볼은 after에 저장한다.

!!여기서!! 같은 위치로 이동하는 파이어볼이 있을 수 있으므로 vector<Fireball> after[][]로 선언하여 (r,c)로 이동하는 파이어볼들을 after[r][c]에 push_back해준다. (이 부분은 다른 분들의 풀이를 살짝 참고했음,,) 

 

모든 파이어볼을 이동시킨 후에는 before를 비워준다. (모두 after로 저장되었으므로)

 

그다음 N*N을 돌면서 after[i][j]를 확인한다. after[i][j]의 사이즈가 0이면 해당 위치에 파이어볼이 한개도 없는 것이므로 그대로 진행하고, 사이즈가 1이면 파이어볼이 1개 위치하고 있다는 것이므로 추가 작업은 필요하지 않고, 해당 파이어볼은 다시 before에 저장한다. after에서는 지우고, 그대로 진행한다.

사이즈가 0, 1도 아닌 2 이상일 때는 해당 위치에 겹치는 파이어볼들이 있다는 뜻이므로 추가 처리를 해준다. 이 부분도 문제의 설명에 따라 그대로 구현하면 된다. 

 

구현 완료! 예제도 모두 통과하였다.

🧨하지만 제출 결과 런타임 에러가 떴고, 내용은 OutofBounds.

 

범위를 벗어난 배열 참조를 했다는 것이므로, 두 눈에 불을 켜고 코드에서 위치를 찾아나갔다.

뭔가 정보를 재저장하는 과정에서 값이 범위를 벗어났을 가능성이 컸을 것으로 생각하고 찾아가다가(생각보다 오랫동안 헤맸음..) 범인은 move()에 있었다.

 

초기 move() 코드

void move(Fireball ball) {
	int r = ball.r;
	int c = ball.c;
	r += dx[ball.d] * ball.s;
	c += dy[ball.d] * ball.s;
	if (r < 0) r += N;
	if (r >= N) r -= N;
	if (c < 0) c += N;
	if (c >= N) c -= N;

	after[r][c].push_back({ r, c, ball.m, ball.s, ball.d });
}

이동한 위치가 0~N-1 범위를 벗어났을 때 범위 안으로 들어오게 하기 위해 +N 또는 -N 연산을 수행해 주었는데, 여기서 놓친 부분이 r과 c를 갱신하는 과정에서 갱신된 값이 -N이나 2N을 훌쩍 넘기게 되면 +N, -N 연산으로는 범위 안으로 들어오지 못한다.

✨속력 ball.s를 N으로 나누어주어 이동한 위치를 근방에서 놀도록 해주었다. (이전에 이것과 비슷한 실수를 한 적이 있었는데 또 반복했다ㅠ.ㅠ 오늘 이후로 무조건 기억하기..!!!!)

 

수정한 move() 코드

void move(Fireball ball) {
	int r = ball.r;
	int c = ball.c;
	int move = ball.s % N;	// **************
	r += dx[ball.d] * move;
	c += dy[ball.d] * move;
	if (r < 0) r += N;
	if (r >= N) r -= N;
	if (c < 0) c += N;
	if (c >= N) c -= N;

	after[r][c].push_back({ r, c, ball.m, ball.s, ball.d });
}

진짜 완료!!🎉

 

🎈Key Point🎈

Fireball struct를 선언하여 정보 저장

vector<Fireball> after[][] 로 선언

이동 위치 범위 처리

 

[전체 코드]

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

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 };
struct Fireball {
	int r, c, m, s, d;
};

vector<Fireball> before;	// 움직이기 전
vector<Fireball> after[51][51];		// 움직인 후

void move(Fireball ball) {
	int r = ball.r;
	int c = ball.c;
	int move = ball.s % N;	// **************
	r += dx[ball.d] * move;
	c += dy[ball.d] * move;
	if (r < 0) r += N;
	if (r >= N) r -= N;
	if (c < 0) c += N;
	if (c >= N) c -= N;

	after[r][c].push_back({ r, c, ball.m, ball.s, ball.d });
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.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;
		before.push_back({ r - 1, c - 1, m, s, d });
	}
	// 입력

	while (K--) {
		for (int i = 0; i < before.size(); i++) {
			auto ball = before[i];
			move(ball);
		}

		before.clear();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (after[i][j].size() == 0) continue;
				if (after[i][j].size() == 1) {
					before.push_back(after[i][j].front());
					after[i][j].clear();
					continue;
				}

				int m = 0, s = 0;
				int all = 0;
				for (int k = 0; k < after[i][j].size(); k++) {
					m += after[i][j][k].m;
					s += after[i][j][k].s;
					if (after[i][j][k].d % 2 == 0) all++;
				}

				m /= 5;
				s /= (after[i][j].size());
				int d = 1;
				if (all == 0 || all == after[i][j].size()) d = 0;
				if (m == 0) {
					after[i][j].clear();
					continue;
				}
				for (int k = 0; k < 4; k++)
					before.push_back({ i, j, m, s, d + k * 2 });

				after[i][j].clear();
			}
		}
	}

	int result = 0;
	for (int i = 0; i < before.size(); i++) {
		result += before[i].m;
	}

	cout << result;
}