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

www.acmicpc.net/problem/20056

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

문제 : 파이어볼이 격자판에 존재하고 상태들을 입력받습니다(좌표,질량,속력,방향) 그리고 파이어볼은 상태의 조건에 맞게 움직입니다. 이때 주어진 단계를 수행합니다(단계는 귀찮아서 안적을게요;;;)

이때 k번의 반복작업을 수행한 후 남아있는 파이어볼의 질량의 합을 구하세요.

 

해설 : 지난 하반기 삼성문제였더라구요,,,,,(어쩐지 씨xxxxx ,,,,빡쎄더라 ㅠㅠㅠㅠ)

이런 문제 풀때 가장 하지 말아야 될 행동 중 첫번째는 대충 문제 이해했다고 바로 키보드에 손올려 놓지 마세요.(절대로)

문제에 주어진 조건에 맞는 변수들과 함수들 로직들을 펜과 종이로 다 정의를 하고 서로간 상관관계를 꼼꼼하게 체크해 놓고 키보드로 가시길 바라겠습니다.

(사실 저도 이게 잘 안되요;;; 머리도 나빠서 ㅠ)

 

1) 격자판과 파이어볼의 정보를 구조체로 정의해 주었습니다. 방향은 dx,dy로 정의해 주었고요.

2) 격자판의 정보를 board[x][y] 안에 저장해 주니 이를 이용해서 변화하는 질량과 속력을 건드려주면 됩니다. 그러나 방향 같은경우는 합쳐진 모든 파이어볼들의 방향을 체크해 주어야 하니 이를 모두 담을 수 있는 vector 를 사용해 주었습니다. 그럼 파이어볼이 나갈때는 순차적으로 vector[0] 를 삭제해 주면 되겠죠.

(먼저 들어온 순서대로 나가는 순서도 순차적일테니까요)

 

3) 그리고 모든 격자를 확인해 줍니다. 파이어볼 개수>=2 인 격자가 존재하면 정보를 업데이트 하고 큐에 넣습니다. 이때 격자안에 정보들을 꼭 업데이트 해주셔야 합니다. 

여러 파이어볼들이 한곳에 모여 질량이 13이 되었다고 가정하면 4개의 파이어볼들은 각 2의 질량을 갖게 됩니다. 그리고 큐에서 빠져나온 후 이동을 할때 전에 있던 격자의 질량에서 빼주어야 되는데, 각 파이어볼들의 질량이 변하게 되었으니 이 값을 빼면 13과 일치하지 않게 되겠죠. 그러니 13->2*(X개) 로 업데이트를 해주는 것 입니다. 후에 다른 파이어볼들이 들어오게 될때 엉망이 되지 않게 해주기 위해

 

4) k 만큼 반복작업을 실행했다면 이제 각 질량들을 더해서 답을 도출해 주면 됩니다.

 

#이해가 안가시면 댓글로 남겨주세요. 최대한 설명해 드리겠습니다. 또는, 저보다 더 쉽고 간략하게 푼 분의 코드를 보는게 더 나을 수도 있습니다.

 

#include<bits/stdc++.h>

using namespace std;

//격자판의 상태
struct info {
	int m, s,cnt;
	vector<int> d;
}board[51][51];

//파이어볼의 상태
struct fireball {
	int x, y, m, s, d;
};

//방향
int dx[] = { -1,-1,0,1,1,1,0,-1 }, dy[] = { 0,1,1,1,0,-1,-1,-1 };

void solve();

int main()
{
	int t = 0;
	//while(t--)
		solve();
}
void solve()
{
	int n, m, k;
	queue<fireball> q;
	cin >> n >> m >> k;

	int r, c, x, y, z;
	for (int i = 0; i < m; i++) {
		cin >> r >> c >> x >> y >> z;
		r--;
		c--;
		board[r][c].m = x;
		board[r][c].s = y;
		board[r][c].d.push_back(z);
		board[r][c].cnt = 1;
		q.push({ r,c,x,y,z });
	}
	for(int p=0;p<k;p++)
	{
		int size = q.size();
		for (int S = 0; S < size; S++) {
			fireball cur = q.front();
			q.pop();

			int tx = cur.x + dx[cur.d] * cur.s;
			int ty = cur.y + dy[cur.d] * cur.s;

			tx = (tx % n);
			ty = (ty % n);
			if (tx < 0)tx += n;
			if (ty < 0)ty += n;

			board[tx][ty].m += cur.m;
			board[tx][ty].d.push_back(cur.d);
			board[tx][ty].s += cur.s;
			board[tx][ty].cnt++;

			board[cur.x][cur.y].m -= cur.m;
			board[cur.x][cur.y].d.erase(board[cur.x][cur.y].d.begin());
			board[cur.x][cur.y].s -= cur.s;
			board[cur.x][cur.y].cnt--;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)
			{
				if (board[i][j].cnt >= 2) {
					int len = 0;
					int qm = board[i][j].m / 5;
					int qs = board[i][j].s / board[i][j].cnt;
					
					if (qm <= 0) {
						board[i][j].m = board[i][j].s = board[i][j].cnt = 0;
						board[i][j].d.clear();
						continue;
					}

					board[i][j].m = qm * 4;
					board[i][j].s = qs * 4;
					for (int u : board[i][j].d) {
						if (u & 1)
							len++;
					}
					int ds = board[i][j].d.size();
					board[i][j].d.clear();
					board[i][j].cnt = 4;

					if (len == 0 || len == ds) {
						q.push({ i,j,qm,qs,0 });
						q.push({ i,j,qm,qs,2 });
						q.push({ i,j,qm,qs,4 });
						q.push({ i,j,qm,qs,6 });
						board[i][j].d.push_back(0);
						board[i][j].d.push_back(2);
						board[i][j].d.push_back(4);
						board[i][j].d.push_back(6);
					}
					else {
						q.push({ i,j,qm,qs,1 });
						q.push({ i,j,qm,qs,3 });
						q.push({ i,j,qm,qs,5 });
						q.push({ i,j,qm,qs,7 });
						board[i][j].d.push_back(1);
						board[i][j].d.push_back(3);
						board[i][j].d.push_back(5);
						board[i][j].d.push_back(7);
					}
				}
				else if (board[i][j].cnt >= 1) {
					int d = board[i][j].d[0];
					q.push({ i,j,board[i][j].m,board[i][j].s,d });
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			ans += board[i][j].m;
	cout << ans;
}