백준 21611 마법사 상어와 블리자드 (C++)

이 문제는 3가지의 함수로 구현할 수 있습니다. 첫 번째는 구슬을 이동하는 move 함수, 두 번째는 연속된 구슬을 폭발시키는 explode 함수, 마지막으로 구슬을 새롭게 배치시키는 make_bids 함수입니다.

구현 시 주의할 점은 구슬이 달팽이 모양으로 배치된 점인데 이는 map<int,pair<int,int>>와 같이 구슬의 위치에 인덱스를 부여하면 인덱스에 접근하는 것으로 달팽이처럼 구슬에 접근할 수 있게 됩니다.

	#include <bits/stdc++.h>
	#define endl '\n';
	#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	using namespace std;
	typedef long long ll;
	typedef unsigned long long ull;
	typedef pair<int,int> pii;
	const int INF=1e9;
	int dx[]={0,-1,1,0,0}, dy[]={0,0,0,-1,1};
	map<int,pii> num; // 구슬의 와 위치를 저장
	void move(vector<vector<int>>& v, vector<vector<int>>& v2) {
	// 구슬의 이동
	int x=v.size()/2, y=v.size()/2-1;
	for(auto [idx, spot] : num) {
	auto [x,y]=spot;
	if(!idx) continue;
	if(!v[x][y]) {
	bool flag=0;
	for(int i=idx+1;i<v.size()*v.size();i++) {
	int nx=num[i].first, ny=num[i].second;
	if(v[nx][ny]) {
	swap(v[x][y],v[nx][ny]);
	flag=1;
	break;
	}
	}
	if(!flag) return;
	}
	}
	}
	int explode(vector<vector<int>>& v) {
	// 4개 이상의 연속된 구슬이 있는 경우 폭발
	vector<int> t(4);
	for(int i=1;i<v.size()*v.size();i++) {
	int target=v[num[i].first][num[i].second], cnt=1;
	if(!target) continue;
	for(int j=i+1;j<v.size()*v.size();j++) {
	if(target==v[num[j].first][num[j].second]) cnt++;
	else break;
	}
	if(cnt>=4) {
	for(int j=i;j<i+cnt;j++)
	if(target==v[num[j].first][num[j].second])
	v[num[j].first][num[j].second]=0;
	t[target]+=cnt;
	}
	}
	return t[1]+t[2]*2+t[3]*3;
	}
	vector<vector<int>> make_bids(vector<vector<int>>& v) {
	// 구슬 변화 함수, 새로운 공간에 저장하여 리턴
	vector<vector<int>> temp(v.size(),vector<int>(v.size()));
	vector<vector<int>> visit(v.size(),vector<int>(v.size()));
	int iidx=1;
	for(int i=1;i<v.size()*v.size();i++) {
	if(visit[num[i].first][num[i].second]) continue;
	int target=v[num[i].first][num[i].second], cnt=1;
	visit[num[i].first][num[i].second]=1;
	if(!target) continue;
	// 연속적인 구슬의 번호와 개수 카운트
	for(int j=i+1;j<v.size()*v.size();j++) {
	if(target==v[num[j].first][num[j].second])
	cnt++, visit[num[j].first][num[j].second]=1;
	else break;
	}
	// 배열 크기를 넘어가지 않을 때까지 새로운 공간에 구슬 배치
	if(iidx<v.size()*v.size())
	temp[num[iidx].first][num[iidx].second]=cnt;
	if(iidx+1<v.size()*v.size())
	temp[num[iidx+1].first][num[iidx+1].second]=target;
	iidx+=2;
	}
	return temp;
	}
	int main(){
	fastio
	//freopen("input.txt","r",stdin);
	int n,m; cin>>n>>m;
	vector<vector<int>> v(n,vector<int>(n));
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	cin>>v[i][j];
	int sx=n/2, sy=n/2;
	vector<vector<int>> v2(n,vector<int>(n));
	int x=n/2,y=n/2,idx=0;
	v2[x][y]=idx;
	num[idx]={x,y};
	int dir[4]={3,2,4,1}, dist=1, didx=0;
	// 구슬마다 인덱스 저장
	while(idx!=n*n) {
	for(int i=0;i<2;i++) {
	if(idx==n*n) break;
	for(int j=0;j<dist;j++) {
	idx++;
	if(idx==n*n) break;
	int nx=x+dx[dir[didx]], ny=y+dy[dir[didx]];
	v2[nx][ny]=idx;
	num[idx]={nx,ny};
	x=nx, y=ny;
	}
	didx++;
	didx%=4;
	}
	dist++;
	}
	int ans=0;
	while(m--) {
	// 블리자드 마법의 방향과 거리를 입력받고 시뮬레이션
	int a,b; cin>>a>>b;
	// 구슬 파괴
	for(int k=1;k<=b;k++) {
	int nx=sx+dx[a]*k, ny=sy+dy[a]*k;
	if(nx>=0 && nx<n && ny>=0 && ny<n) v[nx][ny]=0;
	}
	// 구슬 이동
	move(v,v2);
	// 구슬 폭발 후 이동을 변화가 없을 때까지 반복
	int ret=explode(v);
	move(v,v2);
	ans+=ret;
	while(ret!=0) {
	ret=explode(v);
	ans+=ret;
	move(v,v2);
	}
	// 구슬
	v=make_bids(v);
	}
	cout<<ans;
	return 0;
	}

view raw boj21611.cpp hosted with ❤ by GitHub