[BeakJoon 20056] 마법사 상어와 파이어볼

안녕하세요. 이번 포스팅에서는

백준 20056 마법사 상어와 파이어볼 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

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

 

 

위 링크에서 확인하실 수 있습니다.

 

 

삼성 문제집을 풀고 있는데... 간만에 구현의 매운맛 제대로 느끼고 있습니다.

 

삼성 문제에서 자주 나타나는 특징중에 하나가 인덱스 처리를 깔끔하게 하기가 어렵다는 점인데요.

 

 

문제의 제한을 보시면 s의 범위가 1000까지이고, N의 범위가 50까지임을 알 수 있습니다.

 

사실 이정도 범위면 while loop를 활용해서 원하는 범위 내로 들어올 때까지 돌려도 크게(?) 이상은 없어 보이긴 하는데, 보통 이런 문제는 모듈러 연산을 통해 인덱스를 계산합니다.

 

void magic() {
	for(int j = 0; j < v.size(); j++) {
		fireBall f = v[j];
		int ny = f.r + dir[f.d][0]*f.s, nx = f.c + dir[f.d][1]*f.s;
		if(ny > n) ny%=n;
		if(nx > n) nx%=n;
		if(ny < 1) ny = n-(abs(ny)%n);
		if(nx < 1) nx = n-(abs(nx)%n);
		
		v[j].r = ny;
		v[j].c = nx;
		board[ny][nx]++;
	}
}

 

바로 이 부분인데요. 이 부분을 처리하기가 무척이나 까다롭습니다.

 

저의 경우 ny 혹은 nx가 n보다 크다면, %n을 통하여 n 이하의 수를 만드려 했고, 만약 1보다 작다면, n - (abs(ny or nx)%n)을 통해 다시 1 이상의 수로 만들어주었습니다.

 

이 부분을 처리하셨다면, 나머지 부분은 문제의 요구사항 그대로 구현하시면 됩니다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
typedef struct __node{
	int r, c, m, s, d;	
}fireBall;
vector<fireBall> v;

int board[54][54];
const int dir[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
void magic() {
	for(int j = 0; j < v.size(); j++) {
		fireBall f = v[j];
		int ny = f.r + dir[f.d][0]*f.s, nx = f.c + dir[f.d][1]*f.s;
		if(ny > n) ny%=n;
		if(nx > n) nx%=n;
		if(ny < 1) ny = n-(abs(ny)%n);
		if(nx < 1) nx = n-(abs(nx)%n);
		
		v[j].r = ny;
		v[j].c = nx;
		board[ny][nx]++;
	}
}
void merge() {
	vector<fireBall> newBall;
	for(int i = 0; i < 54; i++) {
		for(int j = 0; j < 54; j++ ){
			if(board[i][j] > 1) {
				int m = 0, s = 0, cnt = 0;
				int dOdd = 0, dEven = 0;
				for(int f = 0; f < v.size(); f++) {
					if(v[f].r == i && v[f].c == j) {
						cnt++;
						m+=v[f].m;
						s+=v[f].s;	
						if(v[f].d %2 == 0) dEven++;
						else dOdd++;
					}
				}
				
				fireBall f1, f2, f3, f4;
				
				m /= 5;
				s /= cnt;
				
				if(m == 0) continue;
				
				f1.m = m, f2.m = m, f3.m = m, f4.m = m;
				f1.s = s, f2.s = s, f3.s = s, f4.s = s;
				f1.r = i, f2.r = i, f3.r = i, f4.r = i;
				f1.c = j, f2.c = j, f3.c = j, f4.c = j;
				
				if(dOdd == cnt || dEven == cnt) {
					f1.d = 0, f2.d = 2, f3.d = 4, f4.d = 6;
				} else {
					f1.d = 1, f2.d = 3, f3.d = 5, f4.d = 7;
				}
				
				newBall.push_back(f1);
				newBall.push_back(f2);
				newBall.push_back(f3);
				newBall.push_back(f4);							
			} else if(board[i][j] == 1) {
				for(int f = 0; f < v.size(); f++) {
					if(v[f].r == i && v[f].c == j) {
						newBall.push_back(v[f]);
					}
				}
			} 
		}
	}
	
	v.clear();
	v.assign(newBall.begin(), newBall.end());
	
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m >> k;
	for(int i = 0; i < m; i++) {
		fireBall f;
		cin >> f.r >> f.c >> f.m >> f.s >> f.d;
		v.push_back(f);
	}
	
	for(int i = 0; i < k; i++) {
		fill(&board[0][0], &board[0][0]+54*54, 0);
		magic();
		merge();
	}
	
	int res = 0;
	for(auto f : v) res += f.m;
	cout << res;
	
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.